#include <bits/stdc++.h>
using namespace std;
const int kN = 1 << 18;
int a[kN];
int64_t ans, f[kN << 1];
bitset<kN> used;
void solve(int l, int r) {
if (l == r) {
++ans;
return;
}
int mid = (l + r) >> 1;
solve(l, mid);
solve(mid + 1, r);
vector<int> candidates;
for (int i = l; i <= r; ++i) {
f[a[i]] = 0;
used[a[i]] = false;
}
for (int i = mid; i >= l; --i) {
if (++f[a[i]] > (mid - i + 1) / 2 && !used[a[i]]) {
candidates.emplace_back(a[i]);
used[a[i]] = true;
}
}
for (int i = l; i <= mid; ++i) {
f[a[i]] = 0;
}
for (int i = mid + 1; i <= r; ++i) {
if (++f[a[i]] > (i - mid) / 2 && !used[a[i]]) {
candidates.emplace_back(a[i]);
used[a[i]] = true;
}
}
int len = r - l + 1;
for (const int &x : candidates) {
for (int i = -len - 1; i <= len + 1; ++i) {
f[i + kN] = 0;
}
int sum = 0;
for (int i = mid; i >= l; --i) {
if (a[i] == x) {
++sum;
} else {
--sum;
}
++f[sum + kN];
}
for (int i = len; i >= -len - 1; --i) {
f[i + kN] += f[i + 1 + kN];
}
sum = 0;
for (int i = mid + 1; i <= r; ++i) {
if (a[i] == x) {
++sum;
} else {
--sum;
}
ans += f[-sum + 1 + kN];
}
}
}
void testCase() {
int n;
cin >> n;
vector<int> v;
v.resize(n);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
v[i - 1] = a[i];
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 1; i <= n; ++i) {
a[i] = distance(v.begin(), lower_bound(v.begin(), v.end(), a[i]));
}
solve(1, n);
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests = 1;
for (int tc = 1; tc <= tests; ++tc) {
testCase();
}
return 0;
}
