#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int N=1e6+10; int n; ll a[N]; #define ls (k<<1) #define rs (k<<1|1) #define lc ls,l,mid #define rc rs,mid+1,r ll xds[N*4]; void pushup(int k) { xds[k]=xds[ls]+xds[rs]; } void add(int k,int l,int r,int pos,ll val) { if(pos==l&&l==r) { xds[k]+=val; return ; } int mid=(l+r)>>1; if(pos<=mid) add(lc,pos,val); else add(rc,pos,val); pushup(k); } ll query(int k,int l,int r,int x,int y) { if(!x||!y) return 0; if(x<=l&&r<=y) return xds[k]; ll ret=0; int mid=(r+l)>>1; if(x<=mid) ret+=query(lc,x,y); if(y>mid) ret+=query(rc,x,y); return ret; } int lst; int main() { scanf("%d",&n); ll ans=0; for(int i=1;i<=n;i++) { scanf("%d",a+i); add(1,1,n,a[i],1); ans+=1ll*i; } lst=0; for(int i=1;i<=n;i++) { if(a[i]>lst) { ans-=query(1,1,n,lst+1,a[i])*1ll*i; lst=a[i]; } add(1,1,n,a[i],-1); } printf("%lld\n",ans); return 0; }