#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 300000
#define mod 1000000007
int ti;
vector<ll> f;
void update(int x){
for (; x <= ti; x = (x | (x + 1))){
f[x]++;
}
}
ll query(int r){
ll ans = 0;
for (; r > 0; r = (r & (r + 1)) - 1){
ans += f[r];
}
return ans;
}
int n;
ll ans = 0;
vector<int> v;
void calc(int x){
f.assign(2 * n + 3, 0);
update(n);
int pr = 0;
for (int i = 1; i <= n; i++){
if (v[i] == x) pr++;
else pr--;
ans += query(pr - 1 + n);
update(pr + n);
}
}
const int bl = 2000;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
v.assign(n + 1, 0);
set<int> se;
map<int, int> ma;
for (int i = 1; i <= n; i++){
cin>>v[i];
se.insert(v[i]);
}
ti = 2 * n + 2;
int no = 1;
for (auto el : se){
ma[el] = no;
no++;
}
vector<int> cn(n + 1, 0), cnt(n + 1, 0);
for (int i = 1; i <= n; i++){
v[i] = ma[v[i]];
}
for (int i = 1; i <= n; i++){
cn[v[i]]++;
if (cn[v[i]] == bl + 1){
calc(v[i]);
}
}
for (int i = 1; i <= n; i++){
int to = min(i + 2 * bl, n), wh = 0;
int ma = 0;
for (int j = i; j <= to; j++){
cnt[v[j]]++;
if (cnt[v[j]] > ma){
ma++;
wh = v[j];
}
if (ma * 2 > (j - i + 1) && cn[wh] <= bl){
ans++;
}
}
for (int j = i; j <= to; j++){
cnt[v[j]]--;
}
}
cout<<ans<<"\n";
}
