solution-code1433

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define LL long long
6
using namespace std;
7
int n,a[50005],b[50005],c[50005];
8
inline int lowbit(int x){return x&(-x);}
9
inline void Add(int x,int v)
10
{
11
  while(x<=50002)c[x]+=v,x+=lowbit(x);
12
  return;
13
}
14
inline LL Query(int x)
15
{
16
  LL sum=0;
17
  while(x>=1)sum+=c[x],x-=lowbit(x);
18
  return sum;
19
}
20
LL f1[50005],f2[50005];
21
inline void LSH()
22
{
23
  int i,num;
24
  memcpy(b,a,sizeof(a));
25
  sort(b+1,b+n+1);
26
  num=unique(b+1,b+n+1)-(b+1);
27
  for(i=1;i<=n;++i)a[i]=lower_bound(b+1,b+num+1,a[i])-b;
28
  return;
29
}
30
int main(void)
31
{
32
  int i;
33
  LL ans=0;
34
  scanf("%d",&n);
35
  for(i=1;i<=n;++i)scanf("%d",&a[i]);
36
  LSH();
37
  for(i=1;i<=n;++i)
38
  {
39
    Add(a[i],1);
40
    f1[i]=Query(a[i]-1);
41
  }
42
  memset(c,0,sizeof(c));
43
  for(i=n;i>=1;--i)
44
  {
45
    Add(a[i],1);
46
    f2[i]=Query(a[i]-1);
47
  }
48
  for(i=1;i<=n;++i)ans+=f1[i]*f2[i];
49
  printf("%lld\n",ans);
50
  return 0;
51
}