样例输入

小埋最近在玩一个解密游戏这个游戏的解密方法是这样的这个游戏会给你提供

个数,让我们求出这

的取模结果。

现在小埋对于这个游戏的解法还是不太理解现在请你帮助小埋解决这个问题。

输入格式

这个题目。

由于是平均数m所以我们可以将所有的数-m求一遍前缀和进行归并排序求出所有的正序对ij,且a[i]a[j])的数对。

代码实现code

mid(lr)/2;merge(l,mid);merge(mid1,r);//归并排序分治int

il,jmid1,totl;while(imidjr){if(a[i]a[j]){ret(mid-i1)%mod;ret%mod;b[tot]a[j];

}else{b[tot]a[i];}}while(imid){b[tot]a[i];

}while(jr){b[tot]a[j];}//区间合并for(int

il;ir;i){a[i]b[i];}

i1;in;i){cinshu[i];shu[i]-m;a[i]

a[i-1]shu[i];}merge(0,n);coutret;return