#include<cstdio> #include<iostream> #define int long long using namespace std; int a,n,b[1000501],cnt,w[1000501],ans; inline int read() { int x=0; char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x; } int ff(int x) { int l=1,r=cnt,mid=(l+r)>>1; while(l<r) { if(b[mid]<=x)l=mid+1; else r=mid; mid=(l+r)>>1; } return w[r]; } signed main() { n=read(); for(int i=1;i<=n;i++) { a=read(); if(a>b[cnt]) { b[++cnt]=a; w[cnt]=i; continue; } if(a==b[cnt])continue; ans+=(i-ff(a)); } printf("%lld",ans); return 0; }