#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int SQRT = 450;
inline void cprs(vector<int> &a){
vector<int> b = a;
sort(b.begin(), b.end());
for (int &x: a)
x = lower_bound(b.begin(), b.end(), x) - b.begin();
}
vector<int> a, cnt;
vector<int> ccnt;
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
a.resize(n);
for (int i=0; i<n; i++)
cin >> a[i];
cprs(a);
cnt.resize(n);
for (int i=0; i<n; i++)
cnt[a[i]]++;
ccnt.resize(n);
ll result = 0;
// Numbers <= SQRT
for (int start=0; start<n; start++){
pair<int, int> pval(-1, -1);
int max_step = min(SQRT*2, n - start + 1);
for (int step=1; step < max_step; step++){
int need = step/2 + 1;
int val = a[start+step-1];
ccnt[val]++;
pval = max(pval, make_pair(ccnt[val], val));
if (pval.first >= need && cnt[pval.second] <= SQRT)
result++;
}
for (int step=1; step < max_step; step++){
int val = a[start+step-1];
ccnt[val]--;
}
}
// Numbers > SQRT
ccnt.resize(n*2+1);
ccnt[n] = 1;
for (int val=0; val<n; val++){
if (cnt[val] <= SQRT) continue;
int prefix = 0;
int pos = n;
for (int i=0; i<n; i++){
if (a[i] == val){
prefix += ccnt[pos];
pos++;
}
else{
pos--;
prefix -= ccnt[pos];
}
result += prefix;
ccnt[pos]++;
}
pos = n;
for (int i=0; i<n; i++){
if (a[i] == val) pos++;
else pos--;
ccnt[pos]--;
}
}
cout << result << "\n";
}
