#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, T = 1000;
bool mark[N];
long long ans;
int n, a[N], cnt[N], seg[N << 3];
void readInput();
void compress();
void pre();
void update(int p, int id = 1, int st = 0, int en = n << 1 | 1);
int get(int l, int r, int id = 1, int st = 0, int en = n << 1 | 1);
long long calc1(int x);
long long calc2(int x);
void solve();
void writeOutput();
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
readInput();
solve();
writeOutput();
return 0;
}
void readInput() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
}
void compress() {
vector<pair<int, int>> v;
for (int i = 0; i < n; i++)
v.push_back({a[i], i});
int tmp = 0;
sort(v.begin(), v.end());
for (int i = 0; i < n - 1; i++)
a[v[i].second] = tmp, tmp += (v[i].first != v[i + 1].first);
a[v[n - 1].second] = tmp;
}
void pre() {
compress();
for (int i = 0; i < n; i++)
cnt[a[i]]++;
}
void update(int p, int id, int st, int en) {
if (en - st == 1) {
seg[id]++;
return;
}
int mid = st + en >> 1;
if (p < mid)
update(p, id << 1, st, mid);
else
update(p, id << 1 | 1, mid, en);
seg[id] = seg[id << 1] + seg[id << 1 | 1];
}
int get(int l, int r, int id, int st, int en) {
if (r <= st || en <= l)
return 0;
if (l <= st && en <= r)
return seg[id];
int mid = st + en >> 1;
return get(l, r, id << 1, st, mid) + get(l, r, id << 1 | 1, mid, en);
}
long long calc1(int x) {
long long res = 0;
for (int len = 1; len <= min(2 * cnt[x], n); len++) {
int num = 0;
for (int i = 0; i < n; i++) {
if (i < len)
num += (a[i] == x);
else {
res += ((len / 2) < num);
num += (a[i] == x) - (a[i - len] == x);
}
}
res += ((len / 2) < num);
}
return res;
}
long long calc2(int x) {
int sum = 0;
long long res = 0;
memset(seg, 0, sizeof seg);
for (int i = 0; i < n; i++) {
sum += 1 - 2 * (a[i] != x);
res += get(0, sum + n) + (0 < sum), update(sum + n);
}
return res;
}
void solve() {
pre();
for (int i = 0; i < n; i++) {
if (mark[a[i]]) continue;
mark[a[i]] = true;
if (cnt[a[i]] < T)
ans += calc1(a[i]);
else
ans += calc2(a[i]);
}
}
void writeOutput() {
cout << ans;
}
