#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
const int base = 2e5;
const int bl = 450;
int n,a[N],b[N],cnt[2*N];
map<int,int>mp;
vector<int>adj[N];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
mp[a[i]]++;
}
int tot = 0;
for(auto it: mp) mp[it.fi] = ++tot;
for(int i = 1; i <= n; i++){
a[i] = mp[a[i]];
adj[a[i]].push_back(i);
}
long long ans = 0;
for(int i = 1; i <= tot; i++){
if(adj[i].size() <= bl){
for(int j = 0; j < adj[i].size(); j++){
for(int k = j; k < adj[i].size(); k++){
int sum = k-j+1;
int len = adj[i][k]-adj[i][j]+1;
if(2*sum > len){
int rem = 2*sum-len-1;
int l;
if(j > 0) l = adj[i][j]-adj[i][j-1]-1;
else l = adj[i][j]-1;
l = min(rem,l);
int r;
if(k+1 < adj[i].size()) r= adj[i][k+1]-adj[i][k]-1;
else r = n-adj[i][k];
r = min(rem,r);
int l1 = 0;
int r1 = min(rem-r-1,l);
if(l1 <= r1) ans += (r1-l1+1)*(r+1);
int l2 = max(0,rem-r);
int r2 = min(l,rem);
if(l2 <= r2) ans += ((rem+1)*(r2-l2+1)-(l2+r2)*(r2-l2+1)/2);
}
}
}
}
else{
for(int j = 1; j <= n; j++){
if(a[j] == i) b[j] = 1;
else b[j] = -1;
}
memset(cnt,0,sizeof(cnt));
int x = base;
int cur = 0;
cnt[base]++;
for(int j = 1; j <= n; j++){
x += b[j];
if(b[j] == 1) cur += cnt[x-1];
else cur -= cnt[x];
ans += cur;
cnt[x]++;
}
}
}
cout << ans;
}
//-----+--+----+-==-=*==--=+----------==----------------+=-----==-=+-==----------------
//---===+=----+=----=*=+=*+----------==-----------+=-----==-----==--+-+----------------
//---+=**=-=+---------***+----=------=-------------=-------+-----==-+--=---------------
//----*+-+++**++------=#+----===-----=-------------=-------==-----+-=+=-+--------------
//----++#***+*+++-----=+-----=-=----+---------------+-------+=-----*=-==-+-------------
//---+=+**++**++++==++*=-----===----+---------------+----=---=-----=*+*=-==------------
//---++**==+--++++++***-----+-+-----+---------------==---==--==-----+**---+------------
//----++*#=-+++***+***------+-+-----+----------------=----+---*+=---=*#=-=-+-----------
//-----=**+++*+++**%++-----=--+-----+----------------=----*=--==+==++***-=+==----------
//-------**#**++*%%@==-----=--+-----+-------------=+++++=-+=---+=+=-=+**--+++----------
//---------====+@@%@-=-----+--+--=+++++--------------=----+==--===---+*---+==+---------
//-----------=@*%%%%-=-----+=-==-----=---------------=----+--=-==+-=-=*----++==--------
//----------%#=%=#%%==-----=+--=-----=---------------+----+--===*=*==**=---+-++--------
//--------+@++@=*@%*-=-----=+=-=-----==-------------++-*%%%***=++-+=-+-+---=-===-------
//-------#%-=%=+@%@+-=-----=+=--+++*==*=------------**@*##%*--=-+-----=+---==-+==------
//------=%+-=%=%*@@--=-----=*#*=+*###@%*---------=+*++%***##=-+-+------+---==-=+=------
//-------%*-=%@+@@+-*=-----+-=--@##*##=+==----------=-#*#***-==-+------+---==--++------
//-------+@=+@@*@*-=-=-----=-==-*#%*##=----------------++=+=----+------+---==--==+-----
//--------%@@%%@*=--+=-----=---+=+#==*-------------------==-----+------+---==---=+-----
//----------%+=#-=--==-----+-------===--------------------------*------+---==---+==----
//---------##-%+-=---=-----++----------------------------------=*------=---==---=+=----
//--------=#-*@=-=---=-----**=----------------=----------------+*------=---==----++----
//-------=@==%*-==---=-----++*---------------------------------*+------+---==----++=---
//------=%*-=@--==---=-----+++*-------------------------------**=------+---==----==+---
//------*#--##--==---=-----+++*+--------------------+--------+**=------+---=-----==+---
//-----=@=--@*---=---=-----+++#+*=--------=+=----=+=-------=#+**-------+---+-----==+---
//----=%+--=@+---=---=-----=+**++**=---------------------=*+****------==---+-----===---
//----*#---*@=---=--==-----=*+#++*+++*=---------------=*#*++#+*+==----+==-+=-----====--
//---=@=---%%----=--=+-----=*+#++*++++***+----------*****+++#**++-----+==-+-------===--
//---%#----%%---==--=+------*+*++*++**+***+**++=+****+==++*+**#-+-----+==-+-------+==--
//--=@=---=%#---==--+*------*++*+*++#+*****++++****+--==*=*****==----===-==-------+==--
//--##----=@*---+=--+*------=++*+*++*++++++*******=-------+***==-----===-==-------+==--
//-=@+----+@=---+=--+#=-----=*+*+*++#++*+++**#*++-+-------+***-+-----+===+--------*==--
//-*@=----*@=---=---+*+------++*+*+*-=++*+***=-+--+--------#**-=-----*====--------*==--
//=%%-----#@---==---=**------++****---------*=----+--------=#=+-----=*==*---------*==--
//=@*-----%@---==---=*#------++*+------=+%@##@+==%%+*+==----+==-----+*+-++++=+++*++==--
