#include <bits/stdc++.h> using namespace std; #define int long long const int N=1e6+10; int a[N],n,seg[N],lzy[N],sm[N],sm2[N]; int f(int x) { return (x*(x+1))/2; } void push(int l=0,int r=2*n,int v=1) { sm2[v]+=sm[v]*lzy[v]; sm[v]+=(r-l+1)*lzy[v]; if(l!=r) { lzy[2*v]+=lzy[v]; lzy[2*v+1]+=lzy[v]; } lzy[v]=0; } void update(int ql,int qr,int ad,int l=0,int r=2*n,int v=1) { if(qr<l or r<ql)return; if(ql<=l and r<=qr) { lzy[v]+=ad; push(l,r,v); return; } push(l,r,v); int m=(l+r)/2; int lc=v<<1,rc=lc|1; update(ql,qr,ad,l,m,lc); update(ql,qr,ad,m+1,r,rc); sm[v]=sm[lc]+sm[rc]; sm2[v]=sm2[lc]+sm2[rc]+sm[rc]*(m-l+1); } int get(int ql,int qr,int l=0,int r=2*n,int v=1) { if(qr<l or r<ql)return 0; push(l,r,v); if(ql<=l and r<=qr) { return sm[v]; } int m=(l+r)/2; int lc=v<<1,rc=lc|1; return get(ql,qr,l,m,lc)+get(ql,qr,m+1,r,rc); } int get2(int ql,int qr,int& ad,int l=0,int r=2*n,int v=1) { if(qr<l or r<ql)return 0; push(l,r,v); if(ql<=l and r<=qr) { int anp=sm2[v]+sm[v]*(ad-1); ad+=(r-l+1); return anp; } int m=(l+r)/2; int lc=v<<1,rc=lc|1; return get2(ql,qr,ad,l,m,lc)+get2(ql,qr,ad,m+1,r,rc); } int32_t main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; long long ans=0; map<int,vector<int>> ind; for(int i=1;i<=n;i++) { cin>>a[i]; ind[a[i]].push_back(i); } for(auto itp:ind) { vector<int> pos=itp.second; update(n,n+pos[0]-1,+1); for(int r=0;r<pos.size();r++) { int sm=(-pos[r] + (r+1)*2) + n; // +n is offset long long cur=get(0,sm-1),oth=0; ans+=cur; int k=((r+1>=pos.size())?(n-pos[r]):(pos[r+1]-pos[r]-1)); int typ=1; oth=get2(sm-k,sm-1,typ); ans+=(cur*k)-oth; update(sm-k,sm,+1); } update(n,n+pos[0]-1,-1); for(int r=0;r<pos.size();r++) { int sm=(-pos[r] + (r+1)*2) + n; // +n is offset int k=((r+1>=pos.size())?(n-pos[r]):(pos[r+1]-pos[r]-1)); update(sm-k,sm,-1); } } cout<<ans<<endl; }