1 /*
 2  树状数组求逆序数
 3 */
 4 #include<stdio.h>
 5 #include<string.h>
 6 #include<stdlib.h>
 7 #define maxn 1000000
 8 int nn;
 9 __int64 tol;
10 int aa[maxn+5];
11 
12 struct node
13 {
14     int id;
15     int val;
16 }stu[maxn+5];
17 //低位操作
18 int lowbit(int x)
19 {
20     return x&(-x);
21 }
22 
23 void ope(int x)
24 {
25     while(x<=nn)
26     {
27         aa[x]++;
28         x+=lowbit(x);
29     }
30 }
31 
32 __int64 sum(int x)
33 {
34      __int64 ans=0;
35     while(x>0)
36     {
37      ans+=aa[x];
38      x-=lowbit(x);
39     }
40     return ans;
41 }
42 int cmp(void const *a,void const *b)
43 {
44     return (*(struct node *)a).val - (*(struct node *)b).val;
45 }
46 int main()
47 {
48     int i,val;
49     while( scanf("%d",&nn)!=EOF)
50     {
51         tol=0;
52         memset(aa,0,sizeof(int)*(nn+5));
53         for(i=0;i<nn;i++)
54         {
55             scanf("%d",&stu[i].val);
56             stu[i].id=i+1;
57         }
58         qsort(stu,nn,sizeof(struct node),cmp);
59         for(i=0;i<nn;i++)
60         {
61             tol+=sum(nn)-sum(stu[i].id);
62             ope(stu[i].id);
63         }
64         printf("%I64d\n",tol);
65     }
66     return 0;
67 }