#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]; queue<int> Q; void Upd(int cur, int vl, int sz){ Q.push(cur); 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); Q.push(cur); } 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(){ ios_base::sync_with_stdio(false); cin.tie(NULL); 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); 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; } } while (Q.size() > 0){ int cr = Q.front(); Q.pop(); Sm[cr] = SmPre[cr] = Lz[cr] = 0; } } cout<<Ans<<'\n'; }