/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
using namespace std;
const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
struct node {
ll val, val1, lazy;
} segtree[8 * mxN];
struct op {
int st, en, val;
};
ll ans;
int n, a[mxN], cnt;
map<int, int> mp;
vi num, appearance[mxN];
ll calc(ll l, ll r) {
ll len = r - l + 1;
return ((l + r) * len / 2);
}
void down(ll idx, ll l, ll r) {
if(segtree[idx].lazy == 0)
return;
ll tmp = segtree[idx].lazy, mid = (l + r) >> 1;
segtree[idx << 1].val += (mid - l + 1) * tmp;
segtree[idx << 1].val1 += calc(1, mid - l + 1) * tmp;
segtree[idx << 1].lazy += tmp;
segtree[idx << 1 | 1].val += (r - mid) * tmp;
segtree[idx << 1 | 1].val1 += calc(1, r - mid) * tmp;
segtree[idx << 1 | 1].lazy += tmp;
segtree[idx].lazy = 0;
}
void merge(node &res, node &a, node &b, ll len) {
res.val = a.val + b.val;
res.val1 = a.val1 * len + b.val1;
}
void update(int l, int r, int idx, int u, int v, int val) {
if(v < l || r < u)
return;
if(u <= l && r <= v) {
segtree[idx].val += (ll)(val) * (ll)(r - l + 1);
segtree[idx].val1 += (ll)(val) * calc(1, r - l + 1);
segtree[idx].lazy += val;
return;
}
down(idx, l, r);
int mid = (l + r) >> 1;
update(l, mid, idx << 1, u, v, val);
update(mid + 1, r, idx << 1 | 1, u, v, val);
merge(segtree[idx], segtree[idx << 1], segtree[idx << 1 | 1], r - mid);
}
ll get_normal(int l, int r, int idx, int u, int v) {
if(v < l || r < u)
return 0;
if(u <= l && r <= v)
return segtree[idx].val;
down(idx, l, r);
int mid = (l + r) >> 1;
return (get_normal(l, mid, idx << 1, u, v) + get_normal(mid + 1, r, idx << 1 | 1, u, v));
}
pll get(int l, int r, int idx, int u, int v) {
// cout << l << " " << r << " " << idx << " " << u << " " << v << endl;
if(v < l || r < u)
return {0, 0};
if(u <= l && r <= v) {
return {segtree[idx].val1, segtree[idx].val};
}
down(idx, l, r);
int mid = (l + r) >> 1;
if(mid < u) return get(mid + 1, r, idx << 1 | 1, u, v);
if(v < mid + 1) return get(l, mid, idx << 1, u, v);
else {
pll tmp = get(l, mid, idx << 1, u, v);
pll tmp1 = get(mid + 1, r, idx << 1 | 1, u, v);
ll len = v - mid;
ll sum = tmp1.ff + tmp.ff + tmp.ss * len;
ll sum1 = tmp.ss + tmp1.ss;
return {sum, sum1};
}
}
ll get_sum(int l, int r) {
// cout << "boom: " << l << " " << r << endl;
if(l == r)
return get_normal(1, 2 * n + 1, 1, 1, l - 1);
pll res = get(1, 2 * n + 1, 1, l, r - 1);
// cout << endl << "l = " << l << ", r - 1 = " << r - 1 << ", res = " << res.ff << endl;
if(l == 1)
return res.ff;
res.ff += get_normal(1, 2 * n + 1, 1, 1, l - 1) * (ll)(r - l + 1);
return res.ff;
}
void solve() {
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
num.pb(a[i]);
}
sort(all(num));
num.erase(unique(all(num)), num.end());
for(int val : num)
mp[val] = ++cnt;
for(int i = 1; i <= n; ++i) {
a[i] = mp[a[i]];
appearance[a[i]].pb(i);
}
for(int i = 1; i <= (int)num.size(); ++i) {
vector<op> ops;
int sz = appearance[i].size();
appearance[i].pb(n + 1);
update(1, 2 * n + 1, 1, n - appearance[i][0] + 2, n + 1, 1);
ops.pb({n - appearance[i][0] + 2, n + 1, -1});
// cout << 0 << " " << n - appearance[i][0] - n + 1 << endl;
int cur_sum = n - appearance[i][0] + 3;
for(int j = 0; j < sz; ++j) {
int cur = appearance[i][j], nxt = appearance[i][j + 1];
int len = nxt - cur, nxt_sum = cur_sum - len + 1;
// cout << cur << ": ";
// cout << cur_sum - n - 1 << " " << nxt_sum - n - 1 << " = ";
ll tmp = get_sum(nxt_sum, cur_sum);
// cout << tmp << endl;
ans += tmp;
update(1, 2 * n + 1, 1, nxt_sum, cur_sum, 1);
ops.pb({nxt_sum, cur_sum, -1});
cur_sum = nxt_sum + 1;
}
for(auto [st, en, val] : ops)
update(1, 2 * n + 1, 1, st, en, val);
// cout << endl;
}
cout << ans << endl;
}
signed main() {
#ifndef CDuongg
if(fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
