#include <bits/stdc++.h>
using namespace std;
/// numar elem maj pe [st, dr], atunci e sigur macar in [st, mij], sau [mij + 1, dr]
const int NMAX(200005), ADD(200005);
using ll = long long;
map<int, int> mp;
int cnt, v[NMAX], viz[NMAX], fr[NMAX], nrSum[2 * NMAX];
ll rez;
inline void solve(int st, int dr){
if(st > dr)
return;
if(st == dr){
++rez;
return;
}
int mij = (st + dr) / 2;
solve(st, mij - 1), solve(mij + 1, dr);
for(int i = st; i <= dr; ++i)
viz[v[i]] = 0, fr[v[i]] = 0;
vector<int> haveCh;
for(int i = mij; i >= st; --i){
++fr[v[i]];
if(fr[v[i]] > (mij - i + 1) / 2 && !viz[v[i]]){
viz[v[i]] = 1;
haveCh.push_back(v[i]);
}
}
for(int i = st; i <= dr; ++i)
fr[v[i]] = 0;
for(int i = mij + 1; i <= dr; ++i){
++fr[v[i]];
if(fr[v[i]] > (i - mij) / 2 && !viz[v[i]]){
viz[v[i]] = 1;
haveCh.push_back(v[i]);
}
}
int lg = dr - st + 1;
for(auto it: haveCh){
for(int i = ADD - lg - 1; i <= ADD + lg + 1; ++i)
nrSum[i] = 0;
int sum = 0;
nrSum[0 + ADD] = 1;
for(int i = st; i < mij; ++i){
if(v[i] == it)
sum ++;
else sum--;
nrSum[sum + ADD]++;
}
for(int i = ADD - lg; i <= ADD + lg; ++i)
nrSum[i] += nrSum[i - 1];
for(int i = mij; i <= dr; ++i){
if(v[i] == it)
sum++;
else sum--;
rez += nrSum[sum + ADD - 1];
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
set<int> s;
for(int i = 1; i <= n; ++i){
cin >> v[i];
s.insert(v[i]);
}
for(auto it: s)
mp[it] = ++cnt;
for(int i = 1; i <= n; ++i)
v[i] = mp[v[i]];
solve(1, n);
cout << rez << '\n';
return 0;
}
