#include <iostream> #include <map> #include <queue> using namespace std; #define int long long const int N = (1<<19) + 1, K = N >> 1; int Lz[N<<1], Sm[N<<1], SmPre[N<<1], a[N]; map<int, int> mp, mp2; vector<int> occ[N]; void Upd(int cur, int vl, int sz){ Lz[cur] += vl; Sm[cur] += vl * sz; SmPre[cur] += vl * (sz * (sz - 1)) / 2; } void Push(int cur, int lc, int rc, int sz){ Upd(lc, Lz[cur], sz); Upd(rc, Lz[cur], sz); Lz[cur] = 0; } void insert(int l, int r, int cur = 1, int st = 1, int en = N){ if (l >= en or r <= st) return; if (l <= st and r >= en){ Upd(cur, 1, en - st); return; } int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2; Push(cur, lc, rc, mid - st); insert(l, r, lc, st, mid); insert(l, r, rc, mid, en); Sm[cur] = Sm[lc] + Sm[rc]; SmPre[cur] = SmPre[lc] + SmPre[rc] + Sm[lc] * (en - mid); } int get(int l, int r, int sum, int cur = 1, int st = 1, int en = N){ if (l >= en or r <= st) return 0; if (l <= st and r >= en) return SmPre[cur] + (en - st) * sum; int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2; Push(cur, lc, rc, mid - st); return get(l, r, sum, lc, st, mid) + get(l, r, sum + Sm[lc], rc, mid, en); } signed main(){ int n, Ans = 0, cur = 0; cin>>n; for (int i=1;i<=n;i++) cin>>a[i], mp[a[i]]; for (auto [i, j] : mp) mp2[i] = ++cur; for (int i=1;i<=n;i++) occ[mp2[a[i]]].push_back(i); for (int i=1;i<=cur;i++){ occ[i].push_back(n + 1); for (int j=1;j<(N<<1);j++) Sm[j] = SmPre[j] = Lz[j] = 0; insert(K, K + 1); int X = K, lst = 0; for (int j : occ[i]){ int len = j - lst - 1; Ans += get(X - len, X, 0); insert(X - len, X); X -= len, X++; if (j <= n){ Ans += get(X, X + 1, 0); insert(X, X + 1); lst = j; } } } cout<<Ans<<'\n'; }