// 01001100 01001111 01010100 01000001 \\ // \\ // ╦ ╔═╗╔╦╗╔═╗ \\ // ║ ║ ║ ║ ╠═╣ \\ // ╩═╝╚═╝ ╩ ╩ ╩ \\ // \\ // 01001100 01001111 01010100 01000001 \\ #include <bits/stdc++.h> using namespace std; #define nl '\n' #define ff first #define ss second #define ll long long #define ld long double #define terminator main #define pll pair<ll,ll> #define add insert #define append push_back #define pii pair<int,int> #define all(x) (x).begin(),(x).end() #define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define mid ((s + e) / 2) #define rc (2 * v + 1) #define lc (2 * v) const int N = 4e5 + 1; int a[N]; int seg[4 * N]; int lazy[4 * N]; void built(int v = 1, int s = 0, int e = N){ if(!seg[v] && !lazy[v] || s == e) return; seg[v] = lazy[v] = 0; built(lc, s, mid); built(rc, mid, e); } void push(int v, int s, int e){ seg[v] += (e - s) * lazy[v]; if(e - s > 1){ lazy[lc] += lazy[v]; lazy[rc] += lazy[v]; } lazy[v] = 0; } void add(int l, int r, int v = 1, int s = 0, int e = N){ push(v, s, e); if(r <= s || e <= l || l >= r) return; if(l <= s && e <= r){ lazy[v]++; push(v, s, e); return; } add(l, r, lc, s, mid); add(l, r, rc, mid, e); seg[v] = seg[lc] + seg[rc]; } int get(int l, int r, int v = 1, int s = 0, int e = N){ push(v, s, e); if(r <= s || e <= l) return 0; if(l <= s && e <= r) return seg[v]; return get(l, r, lc, s, mid) + get(l, r, rc, mid, e); } void solve(){ int n, m, o, p, s; cin >> n; map<int, vector<int>> x; for(int i = 1; i <= n; i++){ cin >> a[i]; x[a[i]].append(i); } ll ans = 0; for(auto & [u, v] : x){ built(); p = 0; s = n; for(auto & j : v){ add(s - j + p + 1, s + 1); m = s - j + p + 2; for(int i = j; i <= n; i++, m--){ if(i != j && a[i] == u) break; o = get(0, m); if(!o) break; ans += o; } s += p - j + 2; p = j; } } cout << ans << nl; } int terminator(){ L0TA; int T = 1; //cin >> T; while(T--) solve(); return 0; }