// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #define int long long
struct fenwickTree{
ll n;
vl BIT;
fenwickTree(int sz){
n = sz;
BIT.resize(n + 1, 0);
}
void update(int i, ll v){
if(i == 0) return;
while(i <= n){
BIT[i] += v;
i += i & (-i);
}
}
ll query(int l, int r){
if(l > r) return 0;
if(l != 1) return query(1, r) - query(1, l - 1);
ll res = 0;
while(r > 0){
res += BIT[r];
r -= r & (-r);
}
return res;
}
};
const int sz = 2e5 + 5;
int a[sz], b[sz], c[sz], pre[sz], cntt[sz], cnt[sz], n, mx, p;
ll res;
vi pos[sz];
fenwickTree t(2 * sz + 5);
void solve(int x){
pre[0] = n + 1;
for(int i = 1; i <= n; i++){
pre[i] = pre[i - 1] + (a[i] == x ? 1 : -1);
}
for(int i = 0; i <= n; i++){
res += t.query(1, pre[i] - 1);
t.update(pre[i], 1);
}
for(int i = 0; i <= n; i++){
t.update(pre[i], -1);
}
}
void fmain(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
b[i] = a[i];
}
sort(b + 1, b + n + 1);
for(int i = 1; i <= n; i++){
if(b[i] != b[i - 1]) c[++p] = b[i];
}
for(int i = 1; i <= n; i++){
int l = 1, r = p, best;
while(l <= r){
int mid = (l + r) / 2;
if(c[mid] >= a[i]){
best = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
a[i] = best;
cnt[a[i]]++;
}
for(int i = 1; i <= p; i++){
if(cnt[i] > 2000) solve(i);
}
for(int i = 1; i <= n; i++){
int to = min(n, i + 4000);
int mx = 0;
for(int j = i; j <= to; j++){
cntt[a[j]]++;
if(cntt[a[j]] > cntt[mx]){
mx = a[j];
}
if(cnt[mx] <= 2000 and mx and cntt[mx] * 2 > (j - i + 1)){
res++;
}
}
for(int j = i; j <= to; j++){
cntt[a[j]]--;
}
}
cout << res;
}
signed main(){
fastio;
int tmr = 1;
// cin >> tmr;
while(tmr--){
fmain();
}
}
