#include <iostream>
#include <map>
#include <queue>
using namespace std;
#define int long long
const int N = (1<<19) + 1, K = N >> 1;
int Lz[N<<1], Sm[N<<1], SmPre[N<<1], a[N];
map<int, int> mp, mp2;
vector<int> occ[N];
queue<int> Q;
void Upd(int cur, int vl, int sz){
Q.push(cur);
Lz[cur] += vl;
Sm[cur] += vl * sz;
SmPre[cur] += vl * (sz * (sz - 1)) / 2;
}
void Push(int cur, int lc, int rc, int sz){
Upd(lc, Lz[cur], sz);
Upd(rc, Lz[cur], sz);
Lz[cur] = 0;
}
void insert(int l, int r, int cur = 1, int st = 1, int en = N){
if (l >= en or r <= st)
return;
if (l <= st and r >= en){
Upd(cur, 1, en - st);
return;
}
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(cur, lc, rc, mid - st);
insert(l, r, lc, st, mid);
insert(l, r, rc, mid, en);
Sm[cur] = Sm[lc] + Sm[rc];
SmPre[cur] = SmPre[lc] + SmPre[rc] + Sm[lc] * (en - mid);
Q.push(cur);
}
int get(int l, int r, int sum, int cur = 1, int st = 1, int en = N){
if (l >= en or r <= st)
return 0;
if (l <= st and r >= en)
return SmPre[cur] + (en - st) * sum;
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(cur, lc, rc, mid - st);
return get(l, r, sum, lc, st, mid) + get(l, r, sum + Sm[lc], rc, mid, en);
}
signed main(){
int n, Ans = 0, cur = 0;
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i], mp[a[i]];
for (auto [i, j] : mp)
mp2[i] = ++cur;
for (int i=1;i<=n;i++)
occ[mp2[a[i]]].push_back(i);
for (int i=1;i<=cur;i++){
occ[i].push_back(n + 1);
insert(K, K + 1);
int X = K, lst = 0;
for (int j : occ[i]){
int len = j - lst - 1;
Ans += get(X - len, X, 0);
insert(X - len, X);
X -= len, X++;
if (j <= n){
Ans += get(X, X + 1, 0);
insert(X, X + 1);
lst = j;
}
}
while (Q.size() > 0){
int cr = Q.front(); Q.pop();
Sm[cr] = SmPre[cr] = Lz[cr] = 0;
}
}
cout<<Ans<<'\n';
}
