ll cnt=0;//记录逆序对数 
ll a[maxn];//原数组
ll b[maxn];//合并时的暂时数组 
void merge(ll  a[],ll l, ll r)//归并排序可以快速的排序还可以记录原数组的逆序对数 
{
    if(l==r)return ;//当递归到区间长度只有1时，返回
    ll mid=(l+r)>>1;
    merge(a,l,mid);
    merge(a,mid+1,r);//分隔成两个区间进行排序
    ll i=l,j=mid+1;//i、j分别指向两个区间的开始
    for(ll k=l;k<=r;k++)
    {
        if(j>r||(i<=mid&&a[i]<=a[j]))   //当右区间遍历完或在左区间没遍历完的情况下左区间指向的元素不大于右区间指向的元素 
        b[k]=a[i++];   //另临时数组获得左区间指向的元素，并指向下一个元素 
     else 
        {     //此时左区间元素小于右区间元素，则左区间的所有剩余元素都与右区间的当前元素构成逆序对 
            cnt+=mid-i+1;
            b[k]=a[j++];
        }    
     } 
      for(ll k=l;k<=r;k++)
      a[k]=b[k];//合并的数组赋值给原数组 
}