#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
const int MXN = 2e5 + 5;
const int B = 450;
int freq[MXN * 2];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n];
for (int &i : a) cin >> i;
map<int, vector<int>> mp;
for (int i = 0; i < n; i++) mp[a[i]].push_back(i);
int res = 0;
for (auto &[val, idx] : mp)
{
if (idx.size() < B)
{
for (int i = 0; i < idx.size(); i++)
{
for (int j = i; j < idx.size(); j++)
{
int sz = idx[j] - idx[i] + 1, cnt = j - i + 1;
if (cnt * 2 <= sz) continue;
int C = cnt * 2 - sz - 1;
int A = min(C, idx[i] - (i ? idx[i - 1] : -1) - 1);
int B = min(C, (j + 1 < idx.size() ? idx[j + 1] : n) - idx[j] - 1);
int l1 = 0, r1 = C - B - 1;
int l2 = C - B, r2 = A;
l1 = max(0LL, l1), r1 = min(r1, A);
l2 = max(0LL, l2), r2 = min(r2, A);
if (l1 <= r1) res += (r1 - l1 + 1) * (B + 1);
if (l2 <= r2)
{
res += (C + 1) * (r2 - l2 + 1);
res -= (l2 + r2) * (r2 - l2 + 1) / 2;
}
}
}
}
else
{
for (int &i : a) i = -1;
for (int &i : idx) a[i] = 1;
int cur = 0, S = 0;
freq[0 + MXN] = 1;
int L = MXN, R = MXN;
for (int &i : a)
{
if (i == 1)
{
cur += freq[S + MXN];
S++;
}
else
{
cur -= freq[S - 1 + MXN];
S--;
}
res += cur;
freq[S + MXN]++;
L = min(L, S + MXN), R = max(R, S + MXN);
}
for (int i = L; i <= R; i++) freq[i] = 0;
}
}
cout << res << '\n';
}
