#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
const int N = 2e5 + 5;
const int B = 450;
int a[N];
int n;
bool sub12() {
return (n <= 2000);
}
bool sub3() {
for (int i = 1; i <= n; ++i)
if (a[i] > 2) return false;
return true;
}
template <typename T>
struct Fenwick {
vector <int> f;
int n;
Fenwick(int _n) {
f.resize(_n + 5);
n = _n;
}
void upd(int x, int val) {
for (; x <= n; x += x & -x)
f[x] += val;
}
int get(int x) {
int ans = 0;
for (; x > 0; x -= x & -x)
ans += f[x];
return ans;
}
};
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#ifdef JASPER
freopen("in1", "r", stdin);
#endif
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
if (sub12()) {
ll ans = 0;
for (int l = 1; l <= n; ++l) {
map <int, int> cnt;
pair <int, int> mx = {0, 0};
for (int r = l; r <= n; ++r) {
cnt[a[r]]++;
if (cnt[a[r]] > mx.second) {
mx = make_pair(a[r], cnt[a[r]]);
}
if (mx.second > (r - l + 1) / 2) {
++ans;
}
}
}
cout << ans << "\n";
return 0;
}
if (sub3()) {
vector <int> prf[3];
for (int i = 1; i <= 2; ++i)
prf[i].resize(n + 5);
for (int i = 1; i <= n; ++i) {
int x = a[i];
prf[1][i] = prf[1][i - 1] + (x == 1);
prf[2][i] = prf[2][i - 1] + (x == 2);
}
vector <int> vals[3];
vals[1].push_back(0);
vals[2].push_back(0);
for (int i = 1; i <= n; ++i) {
vals[1].push_back(2 * prf[1][i] - i);
vals[2].push_back(2 * prf[2][i] - i);
}
sort(vals[1].begin(), vals[1].end());
vals[1].resize(unique(vals[1].begin(), vals[1].end()) - vals[1].begin());
sort(vals[2].begin(), vals[2].end());
vals[2].resize(unique(vals[2].begin(), vals[2].end()) - vals[2].begin());
auto get = [&] (int x, int t) {
return (int) (lower_bound(vals[t].begin(), vals[t].end(), x) - vals[t].begin() + 1);
};
Fenwick <int> f1(n), f2(n);
ll ans = 0;
f1.upd(get(0, 1), 1);
f2.upd(get(0, 2), 1);
for (int r = 1; r <= n; ++r) {
int x1 = get(2 * prf[1][r] - r, 1);
ans += f1.get(x1 - 1);
f1.upd(x1, 1);
int x2 = get(2 * prf[2][r] - r, 2);
ans += f2.get(x2 - 1);
f2.upd(x2, 1);
}
cout << ans << "\n";
return 0;
}
vector <int> vals;
for (int i = 1; i <= n; ++i)
vals.push_back(a[i]);
sort(vals.begin(), vals.end());
vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
int sz = (int) vals.size();
vector <int> cnt(sz, 0);
for (int i = 1; i <= n; ++i) {
a[i] = (int) (lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin());
cnt[a[i]]++;
}
vector <bool> heavy(sz, false);
for (int i = 0; i < sz; ++i) {
if (cnt[i] >= B)
heavy[i] = true;
}
ll ans = 0;
// processing light queries: all elements appear less than sqrt(n)
cnt.assign(sz, 0);
for (int i = 1; i <= n; ++i) {
int mx = 0;
for (int j = i; j <= n && (j - i + 1) / 2 < B; ++j) {
if (!heavy[a[j]]) {
cnt[a[j]]++;
if (cnt[a[j]] > mx) mx = cnt[a[j]];
if (mx > (j - i + 1) / 2) ++ans;
}
}
for (int j = i; j <= n && (j - i + 1) / 2 < B; ++j)
if (!heavy[a[j]]) cnt[a[j]]--;
}
// processing heavy queries: all elements appear at least sqrt(n)
for (int x = 0; x < sz; ++x) {
if (heavy[x]) {
auto get = [&] (int _x) { debug(_x); return _x + n; };
vector <int> prf(n + 5);
for (int i = 1; i <= n; ++i)
prf[i] = prf[i - 1] + (a[i] == x? 1 : -1);
vector <int> f(2 * n + 5, 0);
f[get(0)]++;
ll sum = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] == x)
sum += f[get(prf[i] - 1)];
else
sum -= f[get(prf[i])];
ans += sum;
f[get(prf[i])]++;
}
}
}
cout << ans << "\n";
return 0;
}
