#include <bits/stdc++.h> #define int long long using namespace std; const long long N = 2e5 + 5; int a[N]; int fr[N]; int p[N]; void fk_solution(int n) { map<int, int> mp; mp[0]++; for (int i = 0; i < n; i++) { cin >> a[i]; p[i + 1] = p[i] + (a[i] == 1 ? 1 : -1); // cout << p[i] << endl; mp[p[i + 1]]++; // cout << a[i] << ' ' << p[i + 1] << endl; } // cout << endl; int ans = n * (n + 1) / 2; for (auto &[j, i] : mp) { // cout << j << ' ' << i << endl; ans -= i * (i - 1) / 2; } cout << ans; } void solve() { int n; cin >> n; if (n > 2000) { return fk_solution(n); } int mx = 0; map<int, int> compress; for (int i = 0; i < n; i++) { cin >> a[i]; if (compress[a[i]] == 0) { mx++; compress[a[i]] = mx; } a[i] = compress[a[i]]; } int ans = 0; for (int i = 0; i < n; i++) { map<int, int> fr; multiset<int> s; for (int j = i; j < n; j++) { s.extract(fr[a[j]]); fr[a[j]]++; s.insert(fr[a[j]]); if (*s.rbegin() > (j - i + 1) / 2) { // cout << i + 1 << ' ' << j + 1 << endl; ans++; } } } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { // cout << "Case #" << i << ':' << ' '; solve(); cout << endl; } return 0; }