#include<bits/stdc++.h> #define ll long long #define lb(x) (x&-x) using namespace std; const int N=1e6+10; inline ll read(){ ll x=0,f=1,c=getchar(); while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,a[N],t[N]; inline void add(int x,int k){ for(;x<N;x+=lb(x))t[x]=min(t[x],k); } inline int query(int x,int A=N){ for(;x;x-=lb(x))A=min(A,t[x]); return A; } int main(){ n=read(); for(int i=1;i<=n;i++)a[i]=1000000-read()+1; fill(t+1,t+N,N); ll ans=0; for(int i=1;i<=n;i++){ ll x=query(a[i]-1); if(x!=N)ans+=1ll*i-x; add(a[i],i); } printf("%lld",ans); return 0; }