#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=1000006,inf=0x3f3f3f3f,m=1000005; int n; ll ans; struct Tree { int l,r,mn; } tr[MAXN<<2]; void build(int num,int l,int r) { tr[num].l=l,tr[num].r=r,tr[num].mn=inf; if(l==r) return; const int mid=l+r>>1; build(num<<1,l,mid),build(num<<1|1,mid+1,r); } void update(int num,int x,int y) { tr[num].mn=min(tr[num].mn,y); if(tr[num].l==tr[num].r) return; return update(num<<1|(tr[num<<1].r<x),x,y); } int query(int num,int l,int r) { if(l<=tr[num].l&&tr[num].r<=r) return tr[num].mn; const int ls=num<<1,rs=ls|1; int res=inf; if(l<=tr[ls].r)res=min(res,query(ls,l,r)); if(tr[rs].l<=r)res=min(res,query(rs,l,r)); return res; } int main() { scanf("%d",&n),build(1,1,m); for(int i=1,x,y; i<=n; ++i) { scanf("%d",&x),y=query(1,x+1,m); if(y<inf) ans+=i-y; update(1,x,i); } printf("%lld\n",ans); return 0; }