#include <bits/stdc++.h> using namespace std; const int N=1e6+6; const int M=1e6; const int INF=1e9; int n; inline int Read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } int Mini[N*4]; int A[N]; void Update(int k,int l,int r,int x,int v) { if(l==r&&r==x) { Mini[k]=min(Mini[k],v); return; } int mid=(l+r)>>1; if(x<=mid) Update(k<<1,l,mid,x,v); else Update(k<<1|1,mid+1,r,x,v); Mini[k]=min(Mini[k<<1],Mini[k<<1|1]); } int Query(int k,int l,int r,int x,int y) { if(l>=x&&r<=y) return Mini[k]; int mid=(l+r)>>1,ret=INF; if(x<=mid) ret=min(ret,Query(k<<1,l,mid,x,y)); if(y>mid) ret=min(ret,Query(k<<1|1,mid+1,r,x,y)); return ret; } int main() { n=Read(); memset(Mini,0x3f,sizeof(Mini)); for(int i=1; i<=n; i++) { A[i]=Read(); Update(1,1,M,A[i],i); } long long ans=0; for(int i=1; i<=n; i++) { int k=Query(1,1,M,A[i]+1,M); if(k<i&&k!=INF) ans+=(long long)i-k; } printf("%lld\n",ans); return 0; }