#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); nx=max(nx,0ll); pre=max(pre,0ll); 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)); 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(); } }