#include<iostream>
using namespacestd;
int n, s,a[100005], t[100005], i;
void mergesort(intl, int r) {
if (l == r)
return;
int mid = (l + r) / 2;
int p = l;
int i = l;
int j = mid + 1；
mergesort (l, mid);
mergesort (mid + 1, r);
while (i <= mid && j<= r) {
if (a[j] < a[i]) {
s += mid - i+1;
t[p] = a[j];
p++;
j++;
} else {
t[p] = a[i];
p++;
i++;
}
}
while (i <= mid) {
t[p] = a[i];
p++;
i++;
}
while (j <= r) {
t[p] = a[j];
p++;
j++;
}
for (i = l; i <= r; i++ )
a[i] = t[i];
}
int main() {
cin >> n;
for (i = 1; i <= n; i++)
cin>> a[i];
mergesort (1, n);
cout << s << endl;
return 0;
}
输入:
6
2 6 3 4 5 1
输出：8