#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = (int)2e5 + 50;
const int MX = 450;
int n, a[N], cnt[N], f[2 * N], mk[N], skok[N];
vector<int> vec;
bool was[N];
ll ans;
void upd(int x)
{
for(int i = x; i < 2 * N; i = i | (i + 1)) f[i]++;
}
int get(int x)
{
int res = 0;
for(int i = x; i >= 0; i = (i & (i + 1)) - 1)
res += f[i];
return res;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("input.txt", "r", stdin);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
vec.pb(a[i]);
}
sort(all(vec));
vec.resize(unique(all(vec)) - vec.begin());
int m = sz(vec);
for(int i = 1; i <= n; i++)
{
a[i] = lower_bound(all(vec), a[i]) - vec.begin();
cnt[a[i]]++;
}
for(int i = 0; i < m; i++)
{
if (cnt[i] < MX) continue;
for(int j = 0; j < 2 * N; j++) f[j] = 0;
was[i] = 1;
upd(N);
int pr = 0;
for(int j = 1; j <= n; j++)
{
if (a[j] == i) pr++;
else pr--;
ans += (ll)get(N + pr - 1);
upd(N + pr);
}
}
int id = 1;
for(int i = 1; i <= n; i++)
{
int mx = 0, who = -1;
for(int j = i; j <= min(n, i + MX + MX); j++)
{
if (mk[a[j]] != id)
{
mk[a[j]] = id;
skok[a[j]] = 0;
}
skok[a[j]]++;
if (skok[a[j]] > mx)
{
mx = skok[a[j]];
who = a[j];
}
if (!was[who] && mx > (j - i + 1) / 2)
ans++;
}
id++;
}
cout << ans;
}
