#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF=1e6+1; int dis[(int)1e6+3],a[(int)1e6+3]; struct stu { int Min,l,r; } Tree[(int)4e6+3]; int Read() { int sum=0; char ch=getchar(); while(ch<'0' || ch>'9') ch=getchar(); while(ch>='0' && ch<='9') sum=sum*10+ch-'0',ch=getchar(); return sum; } int Build(int le,int ri,int num) { Tree[num].l=le,Tree[num].r=ri; if(le==ri) { Tree[num].Min=dis[le]; if(!dis[le]) Tree[num].Min=INF; return Tree[num].Min; } int Mid=(le+ri)/2; Tree[num].Min=min(Build(Mid+1,ri,num*2+1),Build(le,Mid,num*2)); return Tree[num].Min; } int Query(int le,int ri,int num,int No,int k) { int mmin=k; if(le==ri) return min(mmin,Tree[num].Min); int Mid=(le+ri)/2; if(Mid>=No) { mmin=min(mmin,Tree[num*2+1].Min); mmin=min(mmin,Query(le,Mid,num*2,No,k)); } if(Mid<No) mmin=min(mmin,Query(Mid+1,ri,num*2+1,No,k)); return mmin; } int main() { int n,Max=0; ll ans=0; n=Read(); for(int i=1; i<=n; ++i) { a[i]=Read(); Max=max(Max,a[i]); dis[a[i]]=i; } Build(1,Max,1); for(int i=1; i<=n; ++i) ans+=i-Query(1,Max,1,a[i],i); cout<<ans<<'\n'; return 0; }