//序列逆序對數,復雜度O(nlogn)
//傳入序列長度和內容,返回逆序對數
//可更改元素類型和比較函數
#include <string.h>
#define MAXN 1000000
#define _cp(a,b) ((a)<=(b))
typedef int elem_t;
elem_t _tmp[MAXN];

int inv(int n,elem_t* a){
	int l=n>>1,r=n-l,i,j;
	int ret=(r>1?(inv(l,a)+inv(r,a+l)):0);
	for (i=j=0;i<=l;_tmp[i+j]=a[i],i++)
		for (ret+=j;j<r&&(i==l||!_cp(a[i],a[l+j]));_tmp[i+j]=a[l+j],j++);
	memcpy(a,_tmp,sizeof(elem_t)*n);
	return ret;
}