#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ordered_set tree<int , null_type , less_equal<int> , rb_tree_tag , tree_order_statistics_node_update>
const int sq=450;
inline void solve()
{
int n;
cin>>n;
int a[n];
map<int,vector<int>>ind;
for (int i=0;i<n;i++)
{
cin>>a[i];
if (ind[a[i]].size()==0)
ind[a[i]].push_back(-1);
ind[a[i]].push_back(i);
}
int ans=0;
for (auto& [po,vec]:ind)
{
if (vec.size()>=sq)
{
ordered_set s;
s.insert(0);
int cnt=0;
for (int i=0;i<n;i++)
{
cnt+=(a[i]==po?1:-1);
int f=s.order_of_key(cnt);
ans+=f;
s.insert(cnt);
}
}
else
{
vec.push_back(n);
int sz=vec.size();
for (int i1=1;i1+1<sz;i1++)
{
ans++;
for (int j1=1;j1<i1;j1++)
{
int i=vec[i1],j=vec[j1];// j.....i
int ex=2*(i1-j1+1)-(i-j+1);/// (csz-(tsz-csz))
if (ex<=0) continue;
ex--;
int nx=vec[i1+1]-vec[i1]-1,pre=vec[j1]-vec[j1-1]-1;
nx=min(nx,ex);
pre=min(pre,ex);
int del=0;
del+=pre;
int st=ex-pre;
int g=min(pre,nx-st);
g=max(g,0ll);
del+=st*g+(g*(g-1))/2;
pre-=g;
pre++;
del+=(pre*nx);
del++;
// cout<<j<<' '<<i<<' '<<del<<endl;
ans+=del;
}
}
}
}
cout<<ans<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t=1;
for (int i=1;i<=t;i++)
{
solve();
}
}
