// #include <bits/stdc++.h> #include <iostream> #include <cmath> #include <algorithm> #include <map> #include <vector> #include <iomanip> #include <string> #include <queue> #include <set> #include <deque> #include <numeric> #include <stack> #include <chrono> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> void fast_io(){ // freopen("", "r", stdin); // freopen("", "w", stdout); ios::sync_with_stdio(0); cin.tie(); cout.tie(); cout << setprecision(9); } #define int long long #define endl '\n' #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define fi first #define se second const int N = 2e5 + 5; int n, rep, A[N]; vector<int> idx[N]; int calculate(int I){ int ans = 0, m = idx[I].size(), sum = 0; int after = m, before = 0; vector<int> a; int init = idx[I][0] - 1; if (init > after){ a.push_back(after - init); } for (int i = 0; i < min(init, after); i++){ a.push_back(-1); } a.push_back(1); after--, before++; for (int i = 1; i < m; i++){ if (idx[I][i] - idx[I][i - 1] - 1 == 0){ a.push_back(1); } else { int total = idx[I][i] - idx[I][i - 1] - 1; int furth = min(total, after); total -= furth; int behin = min(total, before); total -= behin; for (int j = 0; j < behin; j++) a.push_back(-1); if (total != 0) a.push_back(-total); for (int j = 0; j < furth; j++) a.push_back(-1); a.push_back(1); } after--, before++; } init = n - idx[I].back(); before = m; int prev = min(init, before); init -= prev; for (int i = 0; i < prev; i++) a.push_back(-1); if (init > 0) a.push_back(-init); m = a.size(); int s = 0; ordered_set S; S.insert(0); for (int i = 0; i < m; i++){ s += a[i]; ans += S.order_of_key(s); S.insert(s); } return ans; } void solve() { cin >> n; map<int, int> c; for (int i = 1; i <= n; i++){ cin >> A[i]; if (c[A[i]]) A[i] = c[A[i]]; else { c[A[i]] = ++rep; A[i] = rep; } idx[A[i]].push_back(i); } int ans = 0; for (int i = 1; i <= n; i++){ // cout << calculate(i) << endl; if (idx[i].size() == 0) continue; ans += calculate(i); } cout << ans << endl; return; } signed main() { fast_io(); srand(chrono::steady_clock::now().time_since_epoch().count()); int tc = 1; // cin >> tc; while (tc--) solve(); return 0; }