void sort(int left,int right){
        if(left>=right) return;
        int par = nums[left],i = left ,j = right;
        while(i<j){
            while(i<j&&nums[j]>=par) j--;
            if(i<j){
                nums[i] = nums[j];
            }
            while(i<j&&nums[i]<=par) i++;
            if(i<j){
                nums[j] = nums[i];
            } 
        }
        nums[i] = par;
        sort(left,i-1);
        sort(i+1,right);
    }

  void sort(pair[] arr,int l,int r){
        if(l>=r)  return ;
        int mid=(l+r)/2;
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        merge(arr,l,r,mid);
    }
    void merge(pair[] arr,int left,int right,int mid){
       for(int i=left;i<=right;i++) temp[i]=arr[i];
        int i=left,j=mid+1,index=left;// j=mid+1是非常容易错的点
        while(i<=mid||j<=right){
            if(i>mid) arr[index++]=temp[j++];
            else if(j>right) arr[index++]=temp[i++];
            else if(temp[i].val>temp[j].val) arr[index++]=temp[j++];
            else arr[index++]=temp[i++];
        }