// 01001100 01001111 01010100 01000001 \\
// \\
// ╦ ╔═╗╔╦╗╔═╗ \\
// ║ ║ ║ ║ ╠═╣ \\
// ╩═╝╚═╝ ╩ ╩ ╩ \\
// \\
// 01001100 01001111 01010100 01000001 \\
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mid ((s + e) / 2)
#define rc (2 * v + 1)
#define lc (2 * v)
const int N = 4e5 + 1;
int a[N];
int seg[4 * N];
int lazy[4 * N];
void built(int v = 1, int s = 0, int e = N){
if(!seg[v] && !lazy[v] || s == e) return;
seg[v] = lazy[v] = 0;
built(lc, s, mid);
built(rc, mid, e);
}
void push(int v, int s, int e){
seg[v] += (e - s) * lazy[v];
if(e - s > 1){
lazy[lc] += lazy[v];
lazy[rc] += lazy[v];
}
lazy[v] = 0;
}
void add(int l, int r, int v = 1, int s = 0, int e = N){
push(v, s, e);
if(r <= s || e <= l || l >= r) return;
if(l <= s && e <= r){
lazy[v]++;
push(v, s, e);
return;
}
add(l, r, lc, s, mid);
add(l, r, rc, mid, e);
seg[v] = seg[lc] + seg[rc];
}
int get(int l, int r, int v = 1, int s = 0, int e = N){
push(v, s, e);
if(r <= s || e <= l) return 0;
if(l <= s && e <= r) return seg[v];
return get(l, r, lc, s, mid) + get(l, r, rc, mid, e);
}
void solve(){
int n, m, o, p, s;
cin >> n;
map<int, vector<int>> x;
for(int i = 1; i <= n; i++){
cin >> a[i];
x[a[i]].append(i);
}
ll ans = 0;
for(auto & [u, v] : x){
built();
p = 0;
s = n;
for(auto & j : v){
add(s - j + p + 1, s + 1);
m = s - j + p + 2;
for(int i = j; i <= n; i++, m--){
if(i != j && a[i] == u) break;
o = get(0, m);
if(!o) break;
ans += o;
}
s += p - j + 2;
p = j;
}
}
cout << ans << nl;
}
int terminator(){
L0TA;
int T = 1;
//cin >> T;
while(T--)
solve();
return 0;
}
