#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(); } }