// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i, n) for(int i=0; i<(n); ++i)
#define red(i, n) for(int i=(n)-1; i>=0; --i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebearat"
const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll LLinf = 1e18 + 27092008;
const int N = 2e5 + 5;
const int THRESHOLD = 450;
int n, a[N];
int cnt[N], curCnt[N];
void Compress() {
vector<int> com;
FOR(i, 1, n) com.pb(a[i]);
sort(all(com));
com.resize(unique(all(com)) - com.begin());
FOR(i, 1, n)
a[i] = lower_bound(all(com), a[i]) - com.begin() + 1;
}
ll ans = 0;
void lightQuery() {
FOR(i, 1, n) {
int mx = 0;
FOR(j, i, min(i + 2 * THRESHOLD - 1, n)) {
if (cnt[a[j]] <= THRESHOLD) {
curCnt[a[j]]++;
mx = max(mx, curCnt[a[j]]);
}
if (2 * mx > (j - i + 1)) ans++;
}
FOR(j, i, min(i + 2 * THRESHOLD - 1, n))
if (cnt[a[j]] <= THRESHOLD)
curCnt[a[j]]--;
}
}
int arr[N], num[N << 1];
ll dp[N];
void heavyQuery() {
vector<int> heavy;
FOR(i, 1, n)
if (cnt[a[i]] > THRESHOLD) {
heavy.pb(a[i]);
cnt[a[i]] = 0;
}
for(int x : heavy) {
FOR(i, 1, n)
arr[i] = (a[i] == x ? +1 : -1);
memset(num, 0, sizeof num);
memset(dp, 0, sizeof dp);
int pref = n;
num[pref]++;
FOR(i, 1, n) {
pref += arr[i];
if (arr[i] > 0) // pref[i] > pref[i - 1]
dp[i] = dp[i - 1] + num[pref - 1];
else
dp[i] = dp[i - 1] - num[pref];
ans += dp[i];
num[pref]++;
}
}
}
void solve() {
cin >> n;
FOR(i, 1, n) cin >> a[i];
Compress();
FOR(i, 1, n) cnt[a[i]]++;
lightQuery();
heavyQuery();
cout << ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int tc = 1;
// cin >> tc;
while(tc--) solve();
return 0;
}
