#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
const int SQ = 463, M = 2e5 + 5;
int fen[M], cnt1[SQ*3];
int *cnt = cnt1+SQ*2;
void modify(int p)
{
while (p<M)
fen[p]++, p+=p&-p;
}
int get(int p)
{
int ans=0;
while (p)
ans+=fen[p], p^=p&-p;
return ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
int n;
cin>>n;
map<int,vector<int>> ind;
int a[n];
for (int i=0;i<n;i++)
cin>>a[i],ind[a[i]].push_back(i);
ll ans=0;
for (auto [x,v]:ind)
{
if (v.size()<SQ)
{
int m=v.size();
for (int o=0;o<m;o++)
{
int nx=min(n,v[o]+m);
if (o+1<v.size()) nx=min(nx,v[o+1]);
int su=0, st=max(0,v[o]-2*m+1);
cnt[0]++;
for (int i=st;i<v[o];i++)
su+=(a[i]==x)-(a[i]!=x), cnt[su]++;
int t=0;
for (int i=-2*m;i<=su;i++) t+=cnt[i];
ans+=t;
for (int i=v[o]+1;i<nx;i++)
t-=(su<-2*SQ?0:cnt[su]), ans+=t, su--;
for (int i=0;i<SQ*3;i++) cnt1[i]=0;
}
}
else
{
vector<pair<int,int>> v1;
v1.push_back({0,1});
int su=0;
for (int i=0;i<n;i++)
su+=(a[i]==x)-(a[i]!=x), v1.push_back({su,i+2});
sort(all(v1));
for (auto [i,j]:v1)
ans+=get(j), modify(j);
for (int i=0;i<M;i++) fen[i]=0;
}
}
cout<<ans<<endl;
return 0;
}
