#include <bits/stdc++.h>
using namespace std ;
const int MAX = 1e6 + 10 ;
const int B = 448 ;
int arr[MAX] ;
int n ;
vector<int>occ[MAX] ;
void compress()
{
vector<int>v ;
for(int i = 1 ; i <= n ; ++i)
v.push_back(arr[i]) ;
sort(v.begin() , v.end()) ;
v.erase(unique(v.begin() , v.end()) , v.end()) ;
for(int i = 1 ; i <= n ; ++i)
{
arr[i] = lower_bound(v.begin() , v.end() , arr[i]) - v.begin() ;
arr[i]++ ;
}
}
int freq[MAX] ;
long long solve_big(int x)
{
for(int i = 0 ; i <= 3*n ; ++i)
freq[i] = 0 ;
int idx = n-1 , cur = n ;
long long ans = 0 , cnt = 0 ;
freq[n]++ , cnt = 0 ;
for(int i = 1 ; i <= n ; ++i)
{
if(arr[i] == x)
idx++ , cnt += freq[idx] , ++cur ;
else
cnt -= freq[idx] , --idx , --cur ;
ans += cnt ;
freq[cur]++ ;
if(cur <= idx)
cnt++ ;
}
return ans ;
}
long long calc(int l , int r)
{
return (1ll * r * (r+1ll) / 2ll - 1ll * (l-1) * (l) / 2ll) ;
}
long long solve_small(int x)
{
long long ans = 0 ;
int sz = occ[x].size() ;
for(int i = 0 ; i < sz ; ++i)
{
for(int j = 0 ; j <= i ; ++j)
{
int cnt = i-j+1 - (occ[x][i] - occ[x][j] + 1 - (i-j+1)) - 1 ;
int a = occ[x][j] , b = n+1 - occ[x][i] ;
if(j > 0)
a -= occ[x][j-1] ;
if(i+1 < sz)
b = occ[x][i+1] - occ[x][i] ;
if(cnt < 0)
continue ;
// start at occ[x][j]
ans += min(cnt+1 , b) , --a ;
// end at occ[x][i]
ans += min(cnt , a) , --b ;
// start < oxx[x][j] and end > oxx[j][i]
int y = max(0 , min(cnt-a , b)) ;
ans += 1ll * a * y ;
b -= y , cnt -= y ;
ans += calc(cnt - min(cnt , b) , cnt-1) ;
}
}
return ans ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 1 ; i <= n ; ++i)
cin>>arr[i] ;
compress() ;
for(int i = 1 ; i <= n ; ++i)
occ[arr[i]].push_back(i) ;
long long ans = 0 ;
for(int i = 1 ; i <= n ; ++i)
{
if(occ[i].size() >= B)
ans += solve_big(i) ;
else
ans += solve_small(i) ;
}
return cout<<ans<<"\n" , 0 ;
}
