#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n"
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 4e5 + 5;
int fw[N];
void upd(int c){
for(;c<N;c+=c&-c) fw[c]++;
}
int query(int c,int res=0){
for(;c;c-=c&-c) res+=fw[c];
return res;
}
void solve(){
int n;
cin >> n;
int ar[n+1];
for(int i=1;i<=n;i++){
cin >> ar[i];
}
int ans=0;
vector<int> zip;
for(int i=1;i<=n;i++) zip.pb(ar[i]);
sort(all(zip));
zip.erase(unique(all(zip)),zip.end()); // dont forget std::unique function!
for(int i=1;i<=n;i++) ar[i]=upper_bound(all(zip),ar[i])-zip.begin();
const int BL = 500;
int freq[n+1];
memset(freq,0,sizeof(freq));
for(int i=1;i<=n;i++) freq[ar[i]]++;
for(int i=1;i<=n;i++){
if(freq[i]<BL) continue;
int nar[n+1];
for(int j=1;j<=n;j++){
if(ar[j]==i) nar[j]=1;
else nar[j]=-1;
}
memset(fw,0,sizeof(fw));
int cur=0;
upd(cur+n);
for(int j=1;j<=n;j++){
cur+=nar[j];
ans+=query(cur+n-1);
upd(cur+n);
}
}
for(int i=1;i<=2*BL;i++){
if(i>n) continue;
int cfreq[n+1];
pair<int,int> coco={-1,-1};
memset(cfreq,0,sizeof(cfreq));
for(int j=1;j<=n;j++){
cfreq[ar[j]]++;
if(j>i) cfreq[ar[j-i]]--;
if(cfreq[ar[j]]>i/2) coco={ar[j],cfreq[ar[j]]};
if(coco.first!=-1 && cfreq[coco.first]<=i/2) coco={-1,-1};
if(j>=i && coco.first!=-1 && freq[coco.first]<BL) ans++;
}
}
cout << ans << endl;
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int t=1;//cin >> t;
while(t--) solve();
return 0;
}
