#include <bits/stdc++.h> using namespace std; #define int long long #define veci vector<int> #define pb push_back #define res resize #define fin for(int i=0;i<n;i++) cin >> a[i]; int32_t main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; veci a; a.res(n); fin veci b = a; sort(b.begin(), b.end()); veci idx; int ans = 0; int i = 0; while(i<n){ int val = b[i]; idx.clear(); int j=i; while(j<n && b[j]==val){ for(int k=0;k<n;k++){ if(a[k]==val) idx.pb(k); } break; } sort(idx.begin(), idx.end()); int m = idx.size(); for(int x=0;x<m;x++){ for(int y=1;x+y<=m;y++){ int L = idx[x]; int R = idx[x+y-1]; int len = R-L+1; if(y*2<=len) continue; int low = x+y-1; int high = m-1; int best = x+y-1; while(low<=high){ int mid=(low+high)/2; int rr=idx[mid]; int lll=rr-L+1; if(y*2>lll){ best=mid; low=mid+1; }else{ high=mid-1; } } ans += best-(x+y-1)+1; } } while(i<n && b[i]==val) i++; } cout << ans; return 0; }