#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
void fast_io(){
// freopen("", "r", stdin);
// freopen("", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(); cout.tie();
cout << setprecision(9);
}
#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
const int N = 2e3 + 5;
int n, rep, a[N];
vector<int> idx[N];
int calculate(int I){
int ans = 0, m = idx[I].size();
vector<int> a = {};
for (int j = 0; j < idx[I][0] - 1; j++) a.push_back(-1);
a.push_back(1);
for (int i = 1; i < m; i++){
for (int j = 0; j < idx[I][i] - idx[I][i - 1] - 1; j++) a.push_back(-1);
a.push_back(1);
}
for (int j = 0; j < n - idx[I].back(); j++) a.push_back(-1);
m = a.size();
int s = 0;
ordered_set S;
S.insert(0);
for (int i = 0; i < m; i++){
s += a[i];
ans += S.order_of_key(s);
S.insert(s);
}
return ans;
}
void solve() {
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
map<int, int> c;
for (int i = 1; i <= n; i++){
if (c[a[i]]) a[i] = c[a[i]];
else {
c[a[i]] = ++rep;
a[i] = rep;
}
idx[a[i]].push_back(i);
}
int ans = 0;
if (n <= 2000){
for (int l = 1; l <= n; l++){
for (int r = l; r <= n; r++){
for (int i = 1; i <= 50; i++){
int c = a[uniform_int_distribution<int>(l,r)(rng)];
int f = upper_bound(idx[c].begin(),idx[c].end(),r) - lower_bound(idx[c].begin(), idx[c].end(),l);
ans += (f > (r - l + 1) / 2);
if (f > (r - l + 1) / 2) break;
}
}
}
cout << ans << endl;
return;
}
for (int i = 1; i <= n; i++){
// cout << calculate(i) << endl;
if (idx[i].size() == 0) continue;
ans += calculate(i);
}
cout << ans << endl;
return;
}
signed main() {
fast_io();
srand(chrono::steady_clock::now().time_since_epoch().count());
int tc = 1;
// cin >> tc;
while (tc--) solve();
return 0;
}
