#include <bits/stdc++.h> #define N int(1e6+5) #define ll long long using namespace std; int n, x, mx, ret, a[N], seg[N<<2]; ll ans; inline int mn(int a, int b) { return a<b ? a:b; } void pushup(int u) { if(seg[u<<1] && seg[u<<1|1]) seg[u] = mn(seg[u<<1], seg[u<<1|1]); else if(seg[u<<1]) seg[u] = seg[u<<1]; else if(seg[u<<1|1]) seg[u] = seg[u<<1|1]; } void update(int u, int l, int r, int adr, int num) { if(l == r) { if(seg[u] == 0) seg[u] = num; return; } int mid = (l+r)>>1; if(adr <= mid) update(u<<1, l, mid, adr, num); else if(adr > mid) update(u<<1|1, mid+1, r, adr, num); pushup(u); } int query(int u, int l, int r, int s, int t) { if(s<=l && r<=t) return seg[u]; int mid = (l+r)>>1; if(t <= mid) return query(u<<1, l, mid, s, t); if(s >= mid+1) return query(u<<1|1, mid+1, r, s, t); int y = query(u<<1, l, mid, s, t); int z = query(u<<1|1, mid+1, r, s, t); if(y && z) return mn(y, z); if(y) return y; if(z) return z; else return 0; } int main() { scanf("%d", &n); if(n <= 1000) { for(int i=1; i<=n; i++) { scanf("%d", a+i); for(int j=1; j<i; j++) { if(a[j] > a[i]) { ans += i-j; break; } } } printf("%lld\n", ans); return 0; } for(int i=1; i<=n; i++) { scanf("%d", a+i); mx = a[i]>mx ? a[i]:mx; } for(int i=1; i<=n; i++) { update(1, 1, mx, a[i], i); if(i!=1 && a[i]!=mx) { ret = query(1, 1, mx, a[i]+1, mx); if(ret) ans += i-ret; } } printf("%lld\n", ans); return 0; }