#include<iostream> #include<cstdio> #include<algorithm> #include<ctype.h> using namespace std; 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*10+ch-'0'; ch=getchar(); } return x*f; } const int N=1000005,INF=0x7f7f7f7f; int val[N<<2],maxx; void built(int L,int R,int cur) { if(L==R) return val[cur]=INF,void(); int mid=(L+R)>>1; built(L,mid,cur<<1); built(mid+1,R,cur<<1|1); val[cur]=min(val[cur<<1],val[cur<<1|1]); } void modify(int L,int R,int pos,int k,int cur) { if(L==R) return val[cur]=min(val[cur],k),void(); int mid=(L+R)>>1; if(pos<=mid) modify(L,mid,pos,k,cur<<1); else modify(mid+1,R,pos,k,cur<<1|1); val[cur]=min(val[cur<<1],val[cur<<1|1]); } int query(int L,int R,int l,int r,int cur) { if(l<=L&&R<=r) return val[cur]; int mid=(L+R)>>1; if(r<=mid) return query(L,mid,l,r,cur<<1); else if(l>mid) return query(mid+1,R,l,r,cur<<1|1); return min(query(L,mid,l,mid,cur<<1),query(mid+1,R,mid+1,r,cur<<1|1)); } int n,a[N]; long long ans; int main() { n=read(); for(int i=1; i<=n; i++) a[i]=read(),maxx=max(maxx,a[i]+1); built(1,maxx,1); for(int i=1; i<=n; i++) { int qwq=query(1,maxx,a[i]+1,maxx,1); if(qwq!=INF) ans+=i-qwq; modify(1,maxx,a[i],i,1); } printf("%lld\n",ans); return 0; }