#include <bits/stdc++.h> using namespace std; inline int read() { int x=0; bool f=1; char ch=getchar(); while(ch<48||ch>57) { if(ch=='-') f=0; ch=getchar(); } while(ch>=48&&ch<=57) { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); } return f?x:-x; } int n,l,r,mid,maxval[1000005],pos[1000005],a[1000005]; long long ans; int main() { n=read(); for(int i=1; i<=n; i++) { a[i]=read(); if(a[i]>maxval[i-1]) maxval[i]=a[i],pos[i]=i; else maxval[i]=maxval[i-1],pos[i]=pos[i-1]; l=0,r=i; while(l<r-1) { mid=l+r>>1; if(maxval[mid]>a[i]) r=mid; else l=mid; } if(a[i]<maxval[r]) ans+=i-pos[r]; } printf("%lld\n",ans); return 0; }