/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
using namespace std;
const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const int block = 450;
const ll oo = 1e18;
int dp[mxN], fenw[2 * mxN];
int n, a[mxN], cnt[mxN];
map<int, int> num;
map<int, vi> mp;
bool vis[mxN];
ll ans;
void update(int idx, int val) {
while(idx < 2 * mxN) {
fenw[idx] += val;
idx += (idx & (-idx));
}
}
int get(int idx) {
int res = 0;
while(idx) {
res += fenw[idx];
idx -= (idx & (-idx));
}
return res;
}
void calc_light() {
for(int i = 1; i <= n; ++i) {
int max_len = min(n - i + 1, 2 * block), maxx = 0;
vi cur;
for(int len = 1; len <= max_len; ++len) {
int r = i + len - 1;
if(!vis[a[r]]) {
continue;
}
cnt[a[r]]++;
cur.emplace_back(a[r]);
maxx = max(maxx, cnt[a[r]]);
if(maxx * 2 > len) {
++ans;
}
}
for(int &val : cur) {
cnt[val] = 0;
}
}
}
void calc_heavy(vi &v) {
memset(fenw, 0, sizeof fenw);
int cur_sum = mxN, cur_idx = 0;
update(cur_sum, 1);
for(int i = 1; i <= n; ++i) {
if(cur_idx < (int)v.size() && i == v[cur_idx]) {
++cur_sum, ++cur_idx;
}
else {
--cur_sum;
}
ans += get(cur_sum - 1);
update(cur_sum, 1);
}
}
int comp(int val) {
if(num[val] == 0) {
num[val] = num.size();
}
return num[val];
}
void solve() {
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
a[i] = comp(a[i]);
mp[a[i]].emplace_back(i);
}
for(auto &[val, v] : mp) {
if((int)mp[val].size() < block) {
vis[val] = true;
}
else {
calc_heavy(v);
}
}
calc_light();
cout << ans << endl;
}
signed main() {
#ifndef CDuongg
if(fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
