#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5, sq = 777;
ll n, a[N], ans, sm[N * 8];
map <ll, ll> cnt;
vector <ll> mmd, matin;
void read() {
cin >> n;
for (ll t = 0; t < n; t++) {
cin >> a[t];
cnt[a[t]]++;
}
for (auto [x, y] : cnt)
if (y > sq)
mmd.push_back(x);
else
matin.push_back(x);
}
void update(ll id, ll ls, ll le, ll l, ll r, ll x) {
if (ls >= r || le <= l)
return;
if (ls >= l && le <= r) {
sm[id] += x;
return;
}
ll mid = (ls + le) >> 1;
update(id << 1, ls, mid, l, r, x);
update(id << 1 | 1, mid, le, l, r, x);
sm[id] = sm[id << 1] + sm[id << 1 | 1];
}
ll get(ll id, ll ls, ll le, ll l, ll r) {
if (ls >= r || le <= l)
return 0;
if (ls >= l && le <= r)
return sm[id];
ll mid = (ls + le) >> 1;
return get(id << 1, ls, mid, l, r) + get(id << 1 | 1, mid, le, l, r);
}
void solve_big() {
for (ll t = 0; t < mmd.size(); t++) {
ll p[n + 5] = {};
for (ll i = 0; i < n; i++) {
if (a[i] == mmd[t])
p[i + 1] = p[i] + 1;
else
p[i + 1] = p[i] - 1;
}
// cout << "here : " << mmd[t] << '\n';
// for (ll i = 0; i <= n; i++)
// cout << p[i] << ' ';
//
// cout << '\n';
for (int i = 0; i <= n; i++)
p[i] += n + 1;
for (ll i = 0; i <= n; i++) {
update(1, 0, n + n + 5, p[i], p[i] + 1, 1);
ans += get(1, 0, n + n + 5, 0, p[i]);
// cout << "ans : " << ans << '\n';
}
for (ll i = 0; i <= n; i++)
update(1, 0, n + n + 5, p[i], p[i] + 1, -1);
}
}
void solve_small() {
for (ll t = 1; t <= min(n, 2 * sq); t++) {
map <ll, ll> tmp, count;
ll mx = 0;
for (ll i = 0; i < matin.size(); i++) {
count[matin[i]] = 0;
tmp[0]++;
}
for (ll i = 0; i < t; i++) {
if (cnt[a[i]] <= sq) {
tmp[count[a[i]]]--;
count[a[i]]++;
mx = max(mx, count[a[i]]);
tmp[count[a[i]]]++;
}
}
ll pnt = t;
if (mx > t - mx)
ans++;
while (pnt < n) {
if (cnt[a[pnt]] <= sq) {
tmp[count[a[pnt]]]--;
count[a[pnt]]++;
mx = max(mx, count[a[pnt]]);
tmp[count[a[pnt]]]++;
}
if (cnt[a[pnt - t]] <= sq) {
tmp[count[a[pnt - t]]]--;
if (tmp[count[a[pnt - t]]] == 0 && count[a[pnt - t]] == mx)
mx--;
count[a[pnt - t]]--;
tmp[count[a[pnt - t]]]++;
}
if (mx > t - mx)
ans++;
pnt++;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
read();
solve_small();
solve_big();
cout << ans << '\n';
}
