#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pb push_back
#define sz(x) (int)x.size()
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#define el "\n"
using namespace std;
typedef long long ll;
const int N = 2e5 + 500;
const int SQ = 800;
int t[N];
vector <int> vl, vals;
int pf[N], a[N], n, b[N];
vector <int> ps1[N], ps2[N];
ll ans = 0;
void upd(int v, int val) {for (; v < N; v = (v | (v + 1))) t[v] += val;}
int get(int v) {int ret = 0; for (; v >= 0; v = (v & (v + 1)) - 1) ret += t[v]; return ret;}
void calc_big(int x) {
vl.clear();
for (int i = 1; i <= n; i++) {
pf[i] = pf[i - 1] + (x == a[i]);
vl.pb(2 * pf[i - 1] - i + 1);
}
sort(all(vl));
vl.resize(unique(all(vl)) - vl.begin());
for (int i = 1; i <= n; i++) {
b[i] = lower_bound(all(vl), 2 * pf[i - 1] - i + 1) - vl.begin();
upd(b[i], 1);
ans += get(lower_bound(all(vl), 2 * pf[i] - i) - vl.begin() - 1);
}
for (int i = 0; i <= n; i++) {
t[i] = 0;
}
}
ll get_ar(ll a0, ll cnt, ll d) {
return ((2 * a0 + d * (cnt - 1)) * cnt) / 2ll;
}
void calc_small(int x) {
int n = sz(ps1[x]), m = sz(ps2[x]);
for (int i = 1; i < n; i++) {
for (int j = i - 1; j < m - 1; j++) {
int cnt = (j + 1) - i + 1;
int mx_len = min(ps2[x][j + 1] - ps1[x][i - 1] - 1, 2 * cnt - 1);
int mn_len = ps2[x][j] - ps1[x][i] + 1;
if (mn_len > mx_len) {
continue;
}
int R = min(ps2[x][j + 1] - 1, ps1[x][i] + mx_len - 1);
int seg = R - ps2[x][j] + 1;
int ps_l = max(R - mx_len + 1, ps1[x][i - 1] + 1);
ans += max(0ll, (ps1[x][i] - ps_l + 1) * 1ll * seg); /// [ps_l; ps1[i]] = all_segnent
int len = max(0, min((ps_l - 1 - max(ps2[x][j] - mx_len + 1, ps1[x][i - 1] + 1) + 1),
seg - 1));
ans += get_ar(seg - 1, len, -1);
// for (int len = ps2[x][j] - ps1[x][i] + 1; len <= mx_len; len++) {
// cerr << x << " " << i << " " << j << " " << len << " " << max(0, min(ps1[x][i], min(ps1[x][i] + len - 1, ps2[x][j + 1] - 1) - len + 1) - max(ps2[x][j] - len + 1, ps1[x][i - 1] + 1)) + 1 << el;
// ans += max(0, min(ps1[x][i], min(ps1[x][i] + len - 1, ps2[x][j + 1] - 1) - len + 1) - max(ps2[x][j] - len + 1, ps1[x][i - 1] + 1)) + 1;
// }
// cerr << el;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
mt19937 rnd(time(0));
for (int i = 1; i <= n; i++) {
cin >> a[i];
// a[i] = rnd() % 2;
vals.pb(a[i]);
}
sort(all(vals));
vals.resize(unique(all(vals)) - vals.begin());
for (int i = 1; i <= n; i++){
a[i] = lower_bound(all(vals), a[i]) - vals.begin();
ps1[a[i]].pb(i);
ps2[a[i]].pb(i);
}
ll sum = 0;
for (int x = 0; x < min(SQ, sz(vals)); x++) {
sum += (sz(ps1[x]) + 1) * 1ll * (sz(ps1[x]) + 1);
}
for (int x = SQ; x < sz(vals); x++) {
sum += 2ll * n * 17;
}
if (sum < (ll)5e8) {
for (int x = 0; x < sz(vals); x++) {
ps1[x].pb(0);
ps2[x].pb(n + 1);
sort(all(ps1[x]));
if (x < SQ) {
calc_small(x);
} else {
calc_big(x);
}
}
} else {
for (int x = 0; x < sz(vals); x++) {
if (sz(ps1[x]) < SQ) {
ps1[x].pb(0);
ps2[x].pb(n + 1);
sort(all(ps1[x]));
calc_small(x);
} else {
calc_big(x);
}
}
}
cout << ans;
}
