#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)
const int S=450, N=2e5+1, M=N*2+10;
int n, a[N], s[N], t[M];
int cnt[N], mp[N];
void update(int pos, int val){
for (int i=pos; i<M; i+=i&(-i)) t[i]+=val;
}
int get(int pos){
if (pos<0) return 0;
int sum=0;
for (int i=pos; i; i-=i&(-i)) sum+=t[i];
return sum;
}
void solve(){
cin >> n;
long long ans=0;
for (int i=1; i<=n; ++i) cin >> a[i];
vector<int> sus(a+1, a+n+1);
sort(all(sus)); sus.resize(unique(all(sus))-sus.begin());
for (int i=1; i<=n; ++i) a[i]=lower_bound(all(sus), a[i])-sus.begin()+1;
for (int i=1; i<=n; ++i) ++mp[a[i]];
for (int l=1; l<=n; ++l){
int mx=0;
for (int r=l; r<=n && r-l+1<=2*S; ++r){
if (mp[a[r]]<=S){
++cnt[a[r]];
mx=max(mx, cnt[a[r]]);
}
if (mx*2>r-l+1) ++ans;
}
for (int r=l; r<=n && r-l+1<=2*S; ++r){
if (mp[a[r]]<=S) --cnt[a[r]];
}
}
for (int i=1; i<=n; ++i){
if (mp[i]<=S) continue;
memset(s, 0, sizeof s);
memset(t, 0, sizeof t);
for (int j=1; j<=n; ++j) if (a[j]==i) ++s[j]; else --s[j];
partial_sum(s, s+n+1, s);
update(0+n+1, 1);
for (int j=1; j<=n; ++j){
ans+=get(s[j]-1+n+1);
update(s[j]+n+1, 1);
}
}
cout << ans;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int ntests=1;
// cin >> ntests;
while (ntests--) solve();
return 0;
}
