#include <bits/stdc++.h>
using namespace std;
#define oo 1e15
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)
#define int long long
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
const ll base=361;
const ll mod=998244353;
const ld eps=1e-5;
const ll maxn=1e6;
struct segtree_ele{
int val,l,r;
} segtree[10000009];
ll res;
int sizet,l[400009],a[400009],n,i,cnt;
vector<pll> g;
int getnode(int &x) {
if (x==0) {
sizet++;
x=sizet;
segtree[x]={0,0,0};
}
return x;
}
void update(int id,int l,int r,int u) {
if (l>r||r<u||l>u) {
return;
}
if (l==u&&r==u) {
segtree[id].val++;
return;
}
int mid=(r+l)/2;
if (mid<u) {
update(getnode(segtree[id].r),mid+1,r,u);
}
else {
update(getnode(segtree[id].l),l,mid,u);
}
segtree[id].val=segtree[getnode(segtree[id].l)].val+segtree[getnode(segtree[id].r)].val;
}
int get(int id,int l,int r,int u,int v) {
if (l>r||r<u||l>v) {
return 0;
}
if (u<=l&&r<=v) {
return segtree[id].val;
}
int mid=(r+l)/2;
return get(getnode(segtree[id].l),l,mid,u,v)+get(getnode(segtree[id].r),mid+1,r,u,v);
}
int main(){
IO;
cin>>n;
g.push_back({-1,0});
for (i=1;i<=n;i++) {
cin>>a[i];
g.push_back({a[i],i});
}
sort(g.begin(),g.end());
for (i=1;i<=n;i++) {
if (g[i].fi!=g[i-1].fi) {
cnt++;
}
a[g[i].se]=cnt;
}
sizet=0;
getnode(a[0]);
for (i=1;i<=n;i++) {
//cout<<a[i]<<' ';
l[i]=get(1,1,maxn,1,a[i]-1);
update(1,1,maxn,a[i]);
}
//cout<<'\n';
sizet=0;
a[0]=0;
getnode(a[0]);
for (i=n;i>=1;i--) {
//cout<<l[i]<<' '<<get(1,1,maxn,1,a[i]-1)<<'\n';
res+=ll(l[i])*ll(get(1,1,maxn,1,a[i]-1));
update(1,1,maxn,a[i]);
}
cout<<res<<'\n';
}
Compilation message
cc1plus: error: '::main' must return 'int'
