int a[100005];
int t[100005];
// 归并排序
void merge(int l, int r){
	if(l == r) return ;
	// 分解
	int mid = (l+r)/2;
	merge(l, mid);
	merge(mid+1, r);
	// 合并 & 求解
	int i = l, j = mid+1, k = l;
	// 把左右两个区间的元素，分别有序的取出来，放到临时数组中
	while(i<=mid && j<=r){
		// 如果前面的元素较小，就放到临时数组中
		if(a[i]<=a[j]) t[k++] = a[i++];
		else t[k++] = a[j++];
	}
	// 判断左右区间的元素有没有剩余
	while(i<=mid) t[k++] = a[i++];
	while(j<=r)  t[k++] = a[j++];
	// 把临时数组中排好序的元素，再放回到a数组中
	for(int i=l;i<=r;i++) a[i] = t[i];
}