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