#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int n;
int a[maxn];
vector<int> byPosition[maxn];
void read()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
}
int b[maxn];
int pref[maxn];
long long divideAndConquer(int l, int r)
{
if (l > r)
{
return 0;
}
if (l == r)
{
return 1;
}
int mid = (l + r) / 2;
set<int> candidates;
unordered_map<int, int> cnt;
for (int i = mid; i >= l; --i)
{
++cnt[a[i]];
if (cnt[a[i]] > (mid - i) / 2)
{
candidates.insert(a[i]);
}
}
cnt.clear();
for (int i = mid; i <= r; ++i)
{
++cnt[a[i]];
if (cnt[a[i]] > (i - mid + 1) / 2)
{
candidates.insert(a[i]);
}
}
long long ans = 0;
for (auto currentCandidate : candidates)
{
for (int i = l; i <= r; ++i)
{
if (a[i] == currentCandidate)
{
b[i] = +1;
}
else
{
b[i] = -1;
}
}
cnt.clear();
int sum = 0;
++cnt[sum];
for (int i = l; i <= mid - 1; ++i)
{
sum += b[i];
++cnt[sum];
}
int upTo = (r - l + 1);
for (int i = -upTo; i <= upTo; ++i)
{
cnt[i] += cnt[i - 1];
}
for (int i = mid; i <= r; ++i)
{
sum += b[i];
ans += cnt[sum - 1];
}
}
return ans + divideAndConquer(l, mid - 1) + divideAndConquer(mid + 1, r);
}
void solve()
{
cout << divideAndConquer(1, n) << endl;
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
read();
solve();
return 0;
}
