#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;
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;
}
return 0;
}
