1 #include <stdio.h>
2
3 const int MAXN = 500001 ;
4 __int64 a[MAXN] , c[MAXN] , cnt ;
5
6 void Merge( int le, int mid, int rh);
7
8 void MergeSort(int le, int rh){
9
10
11 if (rh>le)
12 {
13 int mid = (le+rh) >> 1;
14 MergeSort(le,mid);
15 MergeSort(mid + 1,rh);
16 Merge(le, mid, rh);
17 }
18 }
19
20 void Merge(int le, int mid, int rh)
21 {
22 int i, j,
23 tmp = 1;
24 for (i = le, j = mid+1; i <= mid && j <= rh; )
25 {
26 if (a[j] < a[i])
27 {
28 c[tmp++] = a[j++];
29 cnt += mid - i + 1; //记录逆序数
30 }
31 else c[tmp++] = a[i++];
32 }
33 while ( j <= rh )
34 c[tmp++] = a[j++];
35 while( i <= mid )
36 c[tmp++] = a[i++];
37
38 for (i = le; i <= rh; ++i)
39 {
40 a[i] = c[i - le + 1];
41 }
42
43 }
44
45
46 int main()
47 {
48 int n , i ;
49
50 while ( scanf("%d", &n) && n != 0 )
51 {
52 for ( i = 0 ; i < n ; i++ )
53 {
54 scanf("%I64d", &a[i]) ;
55 }
56 cnt = 0 ;
57 MergeSort( 0, n - 1 ) ;
58
59 printf("%I64d\n", cnt) ;
60 }
61 return 0 ;
62 }