#include <bits/stdc++.h>
using namespace std;
#define int long long
const int sq=450;
int const N=4e5+10;
int fen[N]={};
void add(int i,int v)
{
while (i<N)
{
fen[i]+=v;
i=(i|(i+1));
}
}
int sm(int r)
{
int ans=0;
while (r>=0)
{
ans+=fen[r];
r=(r&(r+1))-1;
}
return ans;
}
inline void solve()
{
int n=450;
// cin>>n;
int a[n];
map<int,vector<int>>ind;
for (int i=0;i<n;i++)
{
a[i]=1;
// 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)
{
add(n,1);
int cnt=0;
for (int i=0;i<n;i++)
{
cnt+=(a[i]==po?1:-1);
int f=sm(cnt+n-1);
ans+=f;
add(cnt+n,1);
}
for (int i=0;i<N;i++)
fen[i]=0;
}
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++;
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();
}
}
