#include <bits/stdc++.h>
using namespace std;
long long f(int l, int r) {
return 1LL * (l + r) * (r - l + 1) / 2;
}
#define N 200'005
int bit[2 * N]{}, mark[2 * N]{}, timer = 0;
void update(int pos, int val) {
while (pos < 2 * N) {
if (mark[pos] != timer) {
mark[pos] = timer;
bit[pos] = 0;
}
bit[pos] += val;
pos += pos & -pos;
}
}
int get(int pos) {
int ans = 0;
while (pos > 0) {
if (mark[pos] != timer) {
mark[pos] = timer;
bit[pos] = 0;
}
ans += bit[pos];
pos -= pos & -pos;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int &i : a) cin >> i;
auto cc = a;
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
for (int &i : a) {
i = lower_bound(cc.begin(), cc.end(), i) - cc.begin();
}
int m = cc.size();
const int B = 1000;
vector<vector<int>> pos(m);
for (int i = 0; i < n; i++) {
pos[a[i]].push_back(i);
}
long long ans = n;
for (int i = 0; i < m; i++) {
timer++;
if (pos[i].size() > B) {
int sum = N;
update(sum, 1);
for (int j : a) {
if (j == i) sum++;
else sum--;
ans += get(sum - 1);
update(sum, 1);
}
ans -= pos[i].size();
}
else {
for (int l = 0; l < pos[i].size(); l++) {
for (int r = l + 1; r < pos[i].size(); r++) {
int bad = pos[i][r] - pos[i][l] - r + l;
if (bad >= r - l + 1) continue;
int lb = 0, rb = r - l - bad;
int le = (l ? pos[i][l] - pos[i][l - 1] - 1 : pos[i][l]);
int ri = (r + 1 == pos[i].size() ? n - 1 - pos[i][r] : pos[i][r + 1] - pos[i][r] - 1);
le = min(le, rb);
ri = min(ri, rb);
ans += le + 1;
if (rb <= ri) ans += f(rb - le, rb);
else if (rb - le >= ri) ans += ri * (le + 1);
else {
ans += f(rb - le, ri);
ans += (rb - ri) * ri;
}
}
}
}
}
cout << ans;
return 0;
}
