#include<cstdio> #include<cstring> #define rep(a,b,c) for(int c(a);c<=(b);++c) using namespace std; inline int read() { int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar(); while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return res; } template<typename T> inline T Min(const T&x,const T&y){return x<y?x:y;} const int N=1e6+10,W=1e6,INF=0x3f3f3f3f;int t[N],n;long long ans; inline void add(int p,int w){while(p<=W)t[p]=Min(t[p],w),p+=(p&-p);} inline int qry(int p){int r=INF;while(p)r=Min(r,t[p]),p^=(p&-p);return r;} int main() { memset(t,0x3f,sizeof(t)); n=read();rep(1,n,i) { int x=W-read()+1,p=qry(x-1); if(p!=INF)ans+=i-p;add(x,i); } printf("%d\n",ans);return 0; }