#include<bits/stdc++.h> #define I using #define love namespace #define Elaina std I love Elaina; const int N=1000010; int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); } return x*f; } int n,m,a[N],qwq; long long ans; namespace AyaseEli{ int tree[N]; void init(){ memset(tree,0x3f,sizeof(tree)); } int lowbit(int x){ return x&(-x); } void add(int *tree,int x,int v){ while(x<=m)tree[x]=min(tree[x],v),x+=lowbit(x); } int query(int *tree,int x){ int res=0x3f3f3f3f; while(x)res=min(res,tree[x]),x-=lowbit(x); return res; } } I love AyaseEli; int main(){ init(); n=read(); for(int i=1;i<=n;i++)a[i]=read(),m=max(m,a[i]); for(int i=1;i<=n;i++){ a[i]=m-a[i]+1; qwq=query(tree,a[i]-1); if(qwq!=0x3f3f3f3f)ans+=i-qwq; add(tree,a[i],i); } printf("%lld",ans); return 0; }