#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <climits>
#include <random>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
using namespace std;
#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define speed ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
const int mod = (int) 1e9 + 7;
const int N = (int) 2e5 + 5, bruh = 450;
int a[N], n, k;
int cnt[N];
int cnt1[N];
int mp[N * 2 + 1];
signed main(){
speed;
cin >> n;
vector<pair<int, int>> v;
for(int i = 1; i <= n; i++){
cin >> a[i];
v.pb({a[i], i});
}
sort(all(v));
int prev = -1, cur = 0;
for(auto [x, y] : v){
if(x != prev){
++cur;
prev = x;
a[y] = cur;
}
else a[y] = cur;
}
for(int i = 1; i <= n; i++){
cnt[a[i]]++;
}
ll ans = 0;
for(int j = 1; j <= cur; j++){
int sz = cnt[j];
if(sz > bruh){
memset(mp, 0, sizeof(mp));
ll cur = 0, act = 0;
ans = (1LL * (n * (n + 1))) / 2LL;
for(int i = 1; i <= n; i++){
if(a[i] == j) cur--;
else cur++;
mp[cur + n]++;
}
cur = 0;
for(ll i = 1; i <= n; i++){
ans -= mp[act + n];
if(a[i] == j){
cur--;
act--;
}
else{
cur++;
act++;
}
mp[cur + n]--;
}
}
}
for(int i = 1; i <= n; i++){
memset(cnt1, 0, sizeof(cnt1));
int lst = -1, lstA = -1;
for(int j = i; j <= n; j++){
if((j - i + 1) > 2 * bruh) break;
if(a[j] == lstA) lst++;
++cnt1[a[j]];
int sz = (j - i) + 1;
if(lst > (sz / 2) && cnt[lstA] <= bruh) ans++;
else if(cnt1[a[j]] > (sz / 2) && cnt[a[j]] <= bruh){
ans++;
lst = cnt1[a[j]];
lstA = a[j];
}
}
}
cout << ans;
}
