#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
ll mod = 998244353;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll a, ll b)
{
ll res = 1;
while (b>0)
{
if (b&1)
res = (res*a)%mod;
a = (a*a)%mod;
b>>=1;
}
return res;
}
ll gcd(ll x, ll y)
{
if (y==0)
return x;
return gcd(y, x%y);
}
struct dt
{
ll sum1=0, sum2=0, fl=0, l=0, r=0;
dt(){}
};
const ll mx = 1e6;
ll a[mx];
dt st[4*mx];
vector<ll>lazy(mx, 0);
void build(ll l, ll r, ll v)
{
if (l==r)
{
st[v].l = l, st[v].r = r;
return;
}
ll mid = (l+r)/2;
build(l,mid,2*v);
build(mid+1, r, 2*v+1);
}
void push(ll l, ll r, ll v)
{
if (lazy[v]==0) return;
if (lazy[v]==67)
{
st[v].sum1 = 0;
st[v].sum2 = 0;
if (l!=r)
{
lazy[2*v] = 67;
lazy[2*v+1] = 67;
}
lazy[v] = 0;
return;
}
st[v].sum1 += (r-l+1);
st[v].sum2 += (r-l+1)*(r-l+2)/2;
if (l!=r)
{
lazy[2*v] = 1;
lazy[2*v+1] = 1;
}
lazy[v] = 0;
}
dt merge(dt a, dt b)
{
if (a.fl==1) return b;
if (b.fl==1) return a;
dt ret;
ret.l = a.l;
ret.r = b.r;
ret.sum1 = a.sum1+b.sum1;
ret.sum2 = b.sum2 + a.sum2 + a.sum1*(b.r-b.l+1);
return ret;
}
dt getans(ll l, ll r, ll v, ll ql, ll qr)
{
// cout<<l<<" "<<r<<endl;
push(l, r, v);
if (r<ql or l>qr)
{
dt ret;
ret.fl = 1;
return ret;
}
if (l>=ql and r<=qr)
return st[v];
ll mid = (l+r)/2;
return merge(getans(l, mid, 2*v, ql, qr), getans(mid+1, r, 2*v+1, ql, qr));
}
void update(ll l, ll r, ll v, ll ql, ll qr)
{
push(l, r, v);
if (r<ql or l>qr)
return;
if (l>=ql and r<=qr)
{
lazy[v] = 1;
push(l, r, v);
return;
}
ll mid = (l+r)/2;
update(l, mid, 2*v, ql, qr);
update(mid+1, r, 2*v+1, ql, qr);
st[v] = merge(st[2*v], st[2*v+1]);
}
ll add = 200009;
void solve()
{
ll n;
cin>>n;
vector<ll>v(n+1);
for (int i=1 ; i<=n ; i++)
cin>>v[i];
build(1, n+add, 1);
map<ll, vector<ll>>mp;
for (int i=1 ; i<=n ;i++) mp[v[i]].push_back(i);
ll res = 0;
for (auto j:mp)
{
auto it = j.second;
ll pr = 0;
lazy[1] = 67;
update(1, n+add, 1, add, add);
for (int i=0 ; i<it.size() ; i++)
{
if (it[i]!=1 and (i==0 or it[i]-it[i-1]>1))
{
ll lst = ((i!=0)? it[i-1]:0);
ll r = pr-1;
ll l = pr-(it[i]-lst-1);
res += getans(1, n+add, 1, l-1+add, r-1+add).sum2;
res += (r-l+1)*getans(1, n+add, 1, 1, l-2+add).sum1;
update(1, n+add, 1, l+add, r+add);
pr -= (it[i]-lst-1);
}
pr++;
res += getans(1, n+add, 1, 1, pr-1+add).sum1;
update(1, n+add, 1, pr+add, pr+add);
}
if (it[it.size()-1]!=n)
{
ll r = pr-1;
ll l = pr-(n-it[it.size()-1]);
res += getans(1, n+add, 1, l-1+add, r-1+add).sum2;
res += (r-l+1)*getans(1, n+add, 1, 1, l-2+add).sum1;
}
}
cout<<res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll tt = 1;
// cin>>tt;
while (tt--)
{
solve();
}
return 0;
}
