#include<bits/stdc++.h> #define il inline #define ll long long using namespace std; const int maxn=1000010; const int V=1000000; il int read(){ int x=0; char c=getchar(); for(;!(c>='0'&&c<='9');c=getchar()); for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-'0'; return x; } ll ans; int a[maxn],n,Tree[maxn]; int Min(int k){ k=V-k+1;int Mn=(1<<30); for(;k;k-=k&-k) Mn=min(Mn,Tree[k]); return Mn; } void Add(int k,int x){ k=V-k+1; for(;k<=V;k+=k&-k) Tree[k]=min(Tree[k],x); } int main(){ n=read(); memset(Tree,127,sizeof(Tree)); for(int i=1;i<=n;i++) a[i]=read(); int Mx=0; for(int i=1;i<=n;i++){ if(Mx>a[i])ans+=i-Min(a[i]+1); Add(a[i],i),Mx=max(Mx,a[i]); } printf("%lld\n",ans); return 0; }