// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
struct fenwickTree{
int n;
vi BIT;
fenwickTree(int sz){
n = sz;
BIT.resize(n + 1, 0);
}
void update(int i, int v){
if(i == 0) return;
while(i <= n){
BIT[i] += v;
i += i & (-i);
}
}
int query(int l, int r){
if(l > r) return 0;
if(l != 1) return query(1, r) - query(1, l - 1);
int res = 0;
while(r > 0){
res += BIT[r];
r -= r & (-r);
}
return res;
}
};
const int sz = 2e5 + 5;
int a[sz], pre[sz], n, res = 0;
void solve1(int x){
pre[0] = n + 1;
for(int i = 1; i <= n; i++){
pre[i] = pre[i - 1] + (a[i] == x ? 1 : -1);
}
fenwickTree t(3 * n + 5);
for(int i = 0; i <= n; i++){
res += t.query(1, pre[i] - 1);
t.update(pre[i], 1);
}
}
void solve2(int x, int cnt){
for(int j = 1; j <= 2 * cnt - 1; j++){
if(j > n) continue;
int s = 0;
for(int i = 1; i < j; i++){
s += (a[i] == x ? 1 : -1);
}
for(int i = j; i <= n; i++){
s += (a[i] == x ? 1 : -1);
if(s > 0) res++;
s -= (a[i - j + 1] == x ? 1 : -1);
}
}
}
void fmain(){
cin >> n;
map<int, int> cnt;
for(int i = 1; i <= n; i++){
cin >> a[i];
cnt[a[i]]++;
}
for(pii i : cnt){
if(i.second <= 2000) solve2(i.first, i.second);
else solve1(i.first);
}
cout << res;
}
signed main(){
fastio;
int tmr = 1;
// cin >> tmr;
while(tmr--){
fmain();
}
}
