#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=1e6+5; const int N=1e6; int tree[maxn*4],n,a[maxn],ans; void update(int l,int r,int k,int val,int num) { if(l==r) { tree[num] = min(tree[num],val); return ; } if(r<k || l>k) return ; int mid=(l+r)/2; update(l,mid,k,val,num*2); update(mid+1,r,k,val,num*2+1); tree[num] = min(tree[num*2],tree[num*2+1]); } int query(int l,int r,int x,int y,int num) { if(r<x || l>y) return 0x3f3f3f3f3f3f3f3f; if(l>=x && r<=y) return tree[num]; int mid=(l+r)/2; return min(query(l,mid,x,y,num*2),query(mid+1,r,x,y,num*2+1)); } signed main() { memset(tree,0x3f,sizeof(tree)); scanf("%lld",&n); for(int i=1;i<=n;++i) { scanf("%lld",&a[i]); update(1,N,a[i],i,1); int t=query(1,N,a[i]+1,N,1); if(t>i) continue; ans+=(i-t); } printf("%lld",ans); }