#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 10, SQ = 300;
long long n, a[N], ps[N], cnt[N * 2], cnt2[N * 2], ans;
void compress() {
set<long long> s;
map<long long, long long> id;
for (long long i = 0; i < n; i++)
s.insert(a[i]);
for (long long i = 0; !s.empty(); i++) {
id[*s.begin()] = i;
s.erase(s.begin());
}
for (long long i = 0; i < n; i++)
a[i] = id[a[i]];
}
void check(long long x) {
ps[0] = N;
for (long long i = 0; i < n; i++)
ps[i + 1] = ps[i] + (a[i] == x) - (a[i] != x);
long long tmp = 0;
cnt2[ps[n]]++;
for (long long i = n - 1; i >= 0; i--) {
if (ps[i + 1] > ps[i]) tmp += cnt2[ps[i + 1]];
else tmp -= cnt2[ps[i]];
ans += tmp;
cnt2[ps[i]]++;
}
memset(cnt2, 0, sizeof cnt2);
}
void input() {
cin >> n;
for (long long i = 0; i < n; i++)
cin >> a[i];
}
void solve() {
compress();
for (long long i = 0; i < n; i++) {
cnt[a[i]]++;
if (cnt[a[i]] == SQ)
check(a[i]);
}
for (long long i = 0; i < n; i++) {
long long maxi = 0, p = 0;
for (long long j = i; j < min(n, i + SQ * 2); j++) {
cnt2[a[j]]++;
if (maxi < cnt2[a[j]]) maxi = cnt2[a[j]], p = a[j];
if (maxi * 2 > j - i + 1 && cnt[p] < SQ)
ans++;
}
for (long long j = i; j < min(n, i + SQ * 2); j++)
cnt2[a[j]]--;
}
cout << ans;
}
int main() {
ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
input();
solve();
}
