#include<bits/stdc++.h> #define il inline #define rg register #define lst long long #define rgt register int #define N 500050 using namespace std; const int Inf=1e9; il int read() { int s=0,m=0;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();} while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); return m?-s:s; } int n,top;lst Ans; int H[N],stk[N]; il void Calc(rgt x) { rgt le=0,ri=top,mid,ret=0; while(le<=ri) { mid=(le+ri)>>1; if(H[stk[mid]]>x)ret=mid,le=mid+1; else ri=mid-1; } if(!ret)Ans+=top; else Ans+=top-ret+1; } int main() { n=read(); for(rgt i=1;i<=n;++i)H[i]=read(); for(rgt i=1;i<=n;++i) { Calc(H[i]); while(top>0&&H[i]>H[stk[top]])--top; stk[++top]=i; }return printf("%lld\n",Ans),0; }