#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(); vector<int> a = {}; for (int j = 0; j < idx[I][0] - 1; j++) a.push_back(-1); a.push_back(1); for (int i = 1; i < m; i++){ for (int j = 0; j < idx[I][i] - idx[I][i - 1] - 1; j++) a.push_back(-1); a.push_back(1); } for (int j = 0; j < n - idx[I].back(); j++) a.push_back(-1); 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() { mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; map<int, int> c; for (int i = 1; i <= n; 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; if (n <= 2000){ for (int l = 1; l <= n; l++){ int occ[n + 1] = {}, idx = 0; for (int r = l; r <= n; r++){ occ[a[r]]++; if (occ[a[r]] > occ[a[idx]]) idx = r; if (occ[a[idx]] > (r - l + 1) / 2) ans++; } } cout << ans << endl; return; } 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; }