#include using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) #define range(a) a.begin(), a.end() template struct BIT { vector dat; BIT(int n) : dat(n + 1) {} void update(int k, T v) { for (int i = k + 1; i < dat.size(); i += i & -i) { dat[i] += v; } } T query(int k) { T res = 0; for (int i = k + 1; i > 0; i -= i & -i) { res += dat[i]; } return res; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; vector A(N); rep(i, N) cin >> A[i]; vector freq(100001); constexpr int S = 2000; rep(i, N) { freq[A[i]]++; } vector large; rep(i, 100001) { if (freq[i] >= S) { large.push_back(i); } } vector cnt(100001); ll ans = 0; rep(i, N) { pair mx(0, 0); for (int j = i; j < min(i + 2*S+10, N); j++) { cnt[A[j]]++; mx = max(mx, {cnt[A[j]], A[j]}); if (mx.first * 2 > j - i + 1 && freq[mx.second] < S) { ans++; } } for (int j = i; j < min(i + 2*S+10, N); j++) { cnt[A[j]]--; } } for (int v : large) { BIT bit(200200); constexpr int B = 100100; int f = B; bit.update(f, 1); for (int i = 0; i < N; i++) { if (A[i] == v) { f++; } else { f--; } ans += bit.query(f - 1); bit.update(f, 1); } } cout << ans << endl; }