#include <cstdio> #include <iostream> using namespace std; int n,maxn; int a[2000005]; long long ans; struct trrd{ int s[7000005]; void update(int k,int l,int r){ s[k]=min(s[k<<1],s[k<<1|1]); } void build(int k,int l,int r){ if(l==r){ s[k]=1e9; return; } int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); update(k,l,r); } void chg(int k,int l,int r,int x,int y){ if(l==r&&l==x){ s[k]=min(s[k],y); return; } int mid=l+r>>1; if(x<=mid) chg(k<<1,l,mid,x,y); else chg(k<<1|1,mid+1,r,x,y); update(k,l,r); } int qry(int k,int l,int r,int x,int y){ if(x<=l&&r<=y) return s[k]; int mid=l+r>>1; int res=1e9; if(x<=mid) res=min(res,qry(k<<1,l,mid,x,y)); if(y>mid) res=min(res,qry(k<<1|1,mid+1,r,x,y)); return res; } }; trrd t; int main(){ scanf("%d",&n); int i,k; for(i=1;i<=n;i++){ scanf("%d",&a[i]); maxn=max(maxn,a[i]); } t.build(1,1,maxn); t.chg(1,1,maxn,a[1],1); for(i=2;i<=n;i++){ t.chg(1,1,maxn,a[i],i); if(a[i]==maxn) continue; k=t.qry(1,1,maxn,a[i]+1,maxn); if(k!=1e9) ans+=i-k; } printf("%lld\n",ans); return 0; }