CodeForces 61E Enemy is weak

The Romans have attacked again. This time they are much more than the Persians but Shapur is ready to defeat them. He says: "A lion is never afraid of a hundred sheep".

Nevertheless Shapur has to find weaknesses in the Roman army to defeat them. So he gives the army a weakness number.

In Shapur's opinion the weakness of an army is equal to the number of triplets i, j, k such that i < j < k and a_i > a_j > a_k where a_x is the power of man standing at position x. The Roman army has one special trait — powers of all the people in it are distinct.

Help Shapur find out how weak the Romans are.

Input

The first line of input contains a single number n (3 ≤ n ≤ 10⁶) — the number of men in Roman army. Next line contains n different positive integers a_i (1 ≤ i ≤ n, 1 ≤ a_i ≤ 10⁹) — powers of men in the Roman army.

Output

A single integer number, the weakness of the Roman army.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Example
Input
3
3 2 1
Output
1
Input
3
2 3 1
Output
0
Input
4
10 8 3 1
Output
4
Input
4
1 5 4 3
Output
1

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int n;
 6 int sum[1000050];
 7 int a[1000050];
 8 struct node{
 9     int num;
10     int power;
11 }p[1000050];
12 bool cmp(node a,node b)
13 {
14     return a.power<b.power;
15 }
16 bool cmp2(node a,node b)
17 {
18     return a.num<b.num;
19 }
20 int lowbite(int x)
21 {
22     return x&(-x);
23 }
24 int update(int x)
25 {
26     while(x<=n)
27     {
28         sum[x]++;
29         x+=lowbite(x);
30     }
31 }
32 long long int find(int x,int i)
33 {
34     long long int  ans=0;
35     for(int t=x;t>0;t-=lowbite(t))
36     {
37         ans+=sum[t];
38     }
39     long long int  qnx=i-ans;
40     return  qnx*(x-ans);
41 
42 }
43 int main()
44 {
45     cin>>n;
46     for(int i=1;i<=n;i++)
47     {
48         scanf("%d",&p[i].power);
49         p[i].num=i;
50     }
51     sort(p+1,p+1+n,cmp);
52     for(int i=1;i<=n;i++)
53     {
54         p[i].power=i;
55     }
56     sort(p+1,p+n+1,cmp2);
57     long long int ans=0;
58     for(int i=1;i<n;i++)
59     {
60         update(p[i].power);
61         ans+=find(p[i].power,i);
62     }
63     cout<<ans<<endl;
64     return 0;
65 }