#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 7;
const int block = 1000;
struct Fenwick_Tree
{
int bit[maxn*2];
void reset()
{
for(int i = 0; i < maxn*2; i++) bit[i] = 0;
}
void update(int pos , int val)
{
while(pos < maxn*2)
{
bit[pos] += val;
pos += (pos & (-pos));
}
}
int get(int pos)
{
int sum = 0;
while(pos > 0)
{
sum += bit[pos];
pos -= (pos & (-pos));
}
return sum;
}
};
int n, a[maxn];
vector <int> pos[maxn];
void compress()
{
vector <int> val;
for(int i = 1; i <= n; i++)
{
val.push_back(a[i]);
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
for(int i = 1; i <= n; i++)
{
a[i] = upper_bound(val.begin(), val.end(), a[i]) - val.begin();
}
}
ll ans = 0ll;
Fenwick_Tree cnt;
int mark[maxn];
int occ[maxn];
void solve() // subtask full
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
compress();
for(int i = 1; i <= n; i++)
{
pos[a[i]].push_back(i);
}
for(int i = 1; i <= n; i++)
{
if((int)pos[i].size() >= block) // heavy
{
cnt.reset();
cnt.update(0 + maxn , 1);
for(int i = 1; i <= n; i++) mark[i] = 1;
for(int x: pos[i]) mark[x] = -1;
int pref = 0;
for(int i = 1; i <= n; i++)
{
pref += mark[i];
cnt.update(pref + maxn , 1);
ans += cnt.get(pref + maxn - 1);
}
}
}
for(int i = 1; i <= maxn; i++)
{
for(int j = i; j <= min(i+block*2 , n); j++) occ[a[j]] = 0;
int mx = 0;
for(int j = i; j <= min(i+block*2 , n); j++)
{
occ[a[j]]++; mx = max(mx , occ[a[j]]);
if(mx > (j - i + 1)/2) ans++;
}
}
cout << ans << '\n';
/*
if(subtask2::check()) subtask2::solve();
else if(subtask3::check()) subtask3::solve();
else subtaskfull::solve();
*/
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
