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