#include
using namespace std;
int a[1000000];
int temp[1000000];
int count=0;//逆序对的个数
void merge(int left,int mid,int right)
{
int i=left,j=mid+1,k=0;
while (( i<=mid )&& (j<=right))
if (a[i]<=a[j]) temp[k++]=a[i++];
else {
count+=mid+1-i;//关键步骤
temp[k++]=a[j++];
}
while (i<=mid) temp[k++]=a[i++];
while (j<=right) temp[k++]=a[j++];
for (i=0,k=left; k<=right;) a[k++]=temp[i++];
}
void mergeSort(int left,int right)
{
if (left
mergeSort(left, mid);
mergeSort(mid+1, right);
merge(left, mid, right);
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i
mergeSort(0,n-1);
cout<
return 0;
}