#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2")
const int N = 2e5 + 5, T = 1897;
vector<long long> big;
long long ans, n, a[N];
map<long long, long long> mp;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
mp[a[i]]++;
}
for (auto &[x, y]: mp)
if (y >= T)
big.push_back(x);
ordered_set s;
for (long long x: big) {
long long fake[n + 5], sum = 0;
for (int i = 0; i < n; i++)
fake[i] = (a[i] == x? 1: -1);
s.insert({0, -1});
for (int i = 0; i < n; i++) {
sum += fake[i];
ans += i + 1 - s.order_of_key({sum, INT_MIN});
s.insert({sum, i});
}
}
for (int i = 0; i < n; i++) {
long long mx = 0;
mp.clear();
for (int sz = 1; sz <= 2 * T; sz++) {
if (i + sz - 1 >= n)
break;
mp[a[i + sz - 1]]++;
mx = max(mx, mp[a[i + sz - 1]]);
if (mx > sz / 2)
ans++;
}
}
cout << ans;
return 0;
}
