#include <bits/stdc++.h>
using namespace std;
void main_program();
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
main_program();
}
const int maxn = 6e5 + 5;
int THRESHOLD;
int n;
int a[maxn], heavy[maxn];
int _dp[maxn * 2];
map<int, int> cmp;
void main_program(){
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
cmp[a[i]] = 1;
}
int CL = 0; for (auto &[key, value]: cmp) value = CL++;
for (int i = 0; i < n; i++) a[i] = cmp[a[i]];
THRESHOLD = 316;
for (int i = 0; i < n; i++) heavy[a[i]]++;
for (int i = 0; i < n; i++) heavy[i] = (heavy[i] > THRESHOLD);
int* dp = _dp + maxn;
long long res = 0;
// Light
for (int i = 0; i < n; i++){
int mx = 0;
for (int j = 0; j < THRESHOLD * 2 + 2; j++){
if (i + j >= n) break;
if (!heavy[a[i+j]]){
dp[a[i+j]]++;
mx = max(mx, dp[a[i+j]]);
}
if ((mx << 1) > (j+1)) res++;
}
for (int j = 0; j < THRESHOLD * 2 + 2; j++){
if (i + j >= n) break;
if (!heavy[a[i+j]]){
dp[a[i+j]]--;
}
}
}
// Heavy
for (int i = 0; i < n; i++){
if (!heavy[i]) continue;
long long less = 0, crr = 0;
dp[crr]++;
for (int j = 0; j < n; j++){
int val = (a[j] == i) ? 1 : -1;
if (val == 1){
less += dp[crr];
crr++;
}
else{
crr--;
less -= dp[crr];
}
dp[crr]++;
res += less;
}
crr = 0; dp[crr]--;
for (int j = 0; j < n; j++){
int val = (a[j] == i) ? 1 : -1;
crr += val;
dp[crr]--;
}
}
cout << res << "\n";
}
