#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("tune=native,avx2")
//#pragma GCC optimize ("Ofast,unroll-loops,trapv")
//#pragma GCC target ("tune=native")
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
typedef pair<ll, pii> mmj;
#define f first
#define s second
#define mkpr make_pair
#define pque priority_queue
#define pb push_back
#define pf push_front
#define vec vector
#define Yes cout << "Yes\n";
#define YES cout << "YES\n";
#define No cout << "No\n";
#define NO cout << "NO\n";
#define em(x) (bool)(x).empty()
#define all(x) (x).begin(), (x).end()
#define tc int tc;cin >> tc; while(tc--)
#define cps CLOCKS_PER_SEC
#define mmj pair<ll, pii>
//setprecision
//int, vector<int>, greater<int>
const int N = 2e5 + 5, P = 1e9 + 7, T = 500;
int n, m, h, a[N], b[N], tr[N + N], rep[N];
bool mk[N];
map<int, int> cnt, mp;
ll ans;
set<int> st;
void add(int i) {
for(; i < N + N; i += i & -i)
tr[i]++;
}
int get(int i) {
int res = 0;
for(; i; i -= i & -i)
res += tr[i];
return res;
}
void ch(int x) {
int pr = n + 2;
memset(tr, 0, sizeof tr);
add(pr);
for(int i = 0; i < n; i++) {
if(a[i] == x)
pr++;
else
pr--;
ans += get(pr - 1);
add(pr);
}
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 0; i < n; i++) {
cin >> a[i];
cnt[a[i]]++;
st.insert(a[i]);
}
int t = 0;
for(auto v: st)
mp[v] = t++;
for(int i = 0; i < n; i++) {
b[i] = mp[a[i]];
//cout << b[i] << ' ';
int x = cnt[a[i]];
if(cnt[a[i]] > T){
ch(a[i]);
cnt[a[i]] = -1;
mk[i] = 1;
}
else if(x == -1)
mk[i] = 1;
}
int mx;
//cout << '\n';
for(int i = 0; i < n; i++) {
m = min(n, i + T + T + 2);
mx = b[i];
for(int j = i; j < m; j++) {
if(!mk[j]) {
rep[b[j]]++;
if(rep[mx] < rep[b[j]])
mx = b[j];
}
//cout << mx;
if(rep[mx] + rep[mx] > j - i + 1)
ans++;
}
for(int j = i; j < m; j++)
if(!mk[j])
rep[b[j]] = 0;
}
cout << ans;
}
