#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;
}
