#include <bits/stdc++.h> using namespace std; int n,l,r,mid,maxt[1000005],height[1000005],a[1000005]; long long ans; int main() { cin>>>n; for(int i=1; i<=n; i++) { cin>>a[i]; if(a[i]>maxval[i-1]) maxt[i]=a[i],height[i]=i; else maxt[i]=maxt[i-1],height[i]=height[i-1]; l=0,r=i; while(l<r-1) { mid=l+r>>1; if(maxt[mid]>a[i]) r=mid; else l=mid; } if(a[i]<maxt[r]) ans+=i-height[r]; } cout<<ans; return 0; }