#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf32 ((int)1e9 + 7)
#define inf64 ((long long)1e18 + 7)
#define MASK32(x) (1 << (x))
#define MASK64(x) (1ll << (x))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define all(a) begin(a), end(a)
#define isz(a) ((int)a.size())
const int N = 4e5 + 1, S = 670;
int a[N], cnt[N], b[N], cnt1[N];
bool heavy[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> compress;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
compress.push_back(a[i]);
}
sort(all(compress));
compress.erase(unique(all(compress)), end(compress));
for(int i = 1; i <= n; ++i) {
a[i] = upper_bound(all(compress), a[i]) - begin(compress);
++cnt[a[i]];
}
long long res = 0;
for(int i = 1; i <= n; ++i) {
if(cnt[i] <= S) continue;
heavy[i] = 1;
long long s = 0;
for(int j = 1, p = 0; j <= n; ++j) {
if(a[j] == i) {
s += cnt1[p + n];
++cnt1[++p + n];
}
else {
s -= cnt1[p - 1 + n];
++cnt1[--p + n];
}
res += s;
}
for(int j = 1, p = 0; j <= n; ++j) {
p += (a[j] == i);
cnt1[p + n] = 0;
}
}
for(int i = 1; i <= n; ++i) {
for(int j = i, mx = -1; j <= min(i + S * 2 - 1, n); ++j) {
++cnt1[a[j]];
if(mx == -1 || cnt1[mx] < cnt1[a[j]]) mx = a[j];
if(!heavy[mx] && cnt1[mx] * 2 > j - i + 1) ++res;
}
for(int j = i; j <= min(i + S * 2 - 1, n); ++j) cnt1[a[j]] = 0;
}
cout << res;
return 0;
}
