#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #define ll long long using namespace std; const int N=1e6+5; int n,m,a[N],b[N],vis[N],f[N]; ll ans; int lowbit(int x) { return x&(-x); } void insert(int x,int val) { for(; x<=m; x+=lowbit(x)) f[x]=min(f[x],val); } int query(int x) { int res=N; for(; x; x-=lowbit(x)) res=min(res,f[x]); return res; } int main() { int x,val; scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); m=unique(b+1,b+1+n)-b; for(int i=1; i<=m; i++) f[i]=N; for(int i=1; i<=n; i++) { a[i]=lower_bound(b+1,b+1+m,a[i])-b; a[i]=m+1-a[i]; val=query(a[i]-1); if(val<N) ans+=i-val; if(!vis[a[i]]) vis[a[i]]=1,insert(a[i],i); } printf("%lld",ans); return 0; }