#include <bits/stdc++.h> using namespace std; const int N = 1e6,INF = 0x7fffffff; int n,ma,t,minn[4*N],a[N],b[N]; long long sum; void build(int x,int l,int r) { minn[x] = INF; if(l == r) return ; build(x * 2,l,(l + r) / 2); build(x * 2 + 1,(l + r) / 2 + 1,r); } void update(int x,int l,int r,int p,int v) { if(l == r) { minn[x] = min(minn[x],v); return ; } int mid = (l + r) / 2; if(p <= mid) update(x * 2,l,mid,p,v); else update(x * 2 + 1,mid + 1,r,p,v); minn[x] = min(minn[x * 2],minn[x * 2 + 1]); } int qmin(int x,int l,int r,int u,int v) { if(u <= l && r <= v) return minn[x]; int mid = (l + r) / 2,ret = INF; if(u <= mid) ret = qmin(x * 2,l,mid,u,v); if(v > mid) ret = min(ret,qmin(x * 2 + 1,mid + 1,r,u,v)); return ret; } int main() { scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); ma = max(ma,a[i]); } build(1,1,ma); for(int i = 1; i <= n; i++) { t = max(t,a[i]); if(a[i] < t) sum += i - qmin(1,1,ma,a[i] + 1,t); update(1,1,ma,a[i],i); } printf("%lld\n",sum); return 0; }