#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 4e5+5, mod = 1e9+7, inf = 1e18, bl = 400;
int n;
int a[N];
int cnt[N];
int tmp[N];
int bit[N];
int get(int p) {
int idx = p, ans = 0;
while (idx>0) {
ans += bit[idx];
idx -= (idx&(-idx));
}
return ans;
}
void upd(int u, int v) {
int idx = u;
while (idx<N) {
bit[idx]+=v;
idx+=(idx&(-idx));
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
vector<int> v;
for (int i=1; i<=n; i++) {
cin >> a[i];
v.pb(a[i]);
}
sort(all(v)); v.erase(unique(all(v)), v.end());
for (int i=1; i<=n; i++) {
a[i] = lower_bound(all(v), a[i])-v.begin()+1;
cnt[a[i]]++;
}
int ans = 0;
for (int i=1; i<=n; i++) {
int mx = 0, idx = 0;
for (int j=i; j<=min(i+2*bl-1, n); j++) {
tmp[a[j]]++;
if (tmp[a[j]]>mx) {
mx = tmp[a[j]];
idx = a[j];
}
if (mx*2>j-i+1 && cnt[idx]<=bl) ans++;
}
for (int j=i; j<=min(i+2*bl-1, n); j++) tmp[a[j]]--;
}
for (int num=1; num<=n; num++) {
if (cnt[num]<=bl) continue;
int dif = 0;
upd(dif+n+1, 1);
for (int i=1; i<=n; i++) {
if (a[i]==num) dif++;
else dif--;
ans += get(dif+n+1-1);
upd(dif+n+1, 1);
}
for (int i=0; i<N; i++) bit[i] = 0;
}
cout << ans;
}
