#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//using LL = __int128
int n, a[100010], cnt[12][100010], maxn; 
int pos[2][100010], t[2];
int calc(int k, int l, int r){
	return cnt[k][r] - cnt[k][l - 1];
}
ll solve(int l, int r){
	if(l == r)
		return 1;
	int mid = (l + r) / 2;
	ll ans = solve(l, mid) + solve(mid + 1, r);
	for(int col = 1 ; col <= maxn ; col++){
		t[0] = t[1] = 0;
		for(int i = l ; i <= mid ; i++)
			pos[0][++t[0]] = 2 * calc(col, i, mid) + i - 2;
		for(int i = mid + 1 ; i <= r ; i++)
			pos[1][++t[1]] = i - 2 * calc(col, mid + 1, i);
		sort(pos[0] + 1, pos[0] + 1 + t[0]);
		sort(pos[1] + 1, pos[1] + 1 + t[1]);
		for(int i = 1 ; i <= t[0] ; i++){
			int pos1 = upper_bound(pos[1] + 1, pos[1] + 1 + t[1], pos[0][i]) - pos[1];
			ans += pos1 - 1;
		}
	}
	return ans;
}
int main(){
	scanf("%lld", &n);
	for(int i = 1 ; i <= n ; i++){
		scanf("%lld", a + i);
		maxn = max(maxn, a[i]);
		for(int j = 1 ; j <= 10 ; j++)
			cnt[j][i] = cnt[j][i - 1];
		cnt[a[i]][i]++;
	}
	if(n <= 1000){
		ll ans = n;
		for(int i = 1 ; i <= n ; i++){
			for(int j = i + 1 ; j <= n ; j++)
				for(int k = 1 ; k <= 10 ; k++)
					if(cnt[k][j] - cnt[k][i - 1] > ((j - i + 1) >> 1)){
						ans++;
						break;
					}
		}
		printf("%lld", ans);
		exit(0);
	}
	printf("%lld", solve(1, n));
	return 0;
}