#include <stdio.h>
#include <string.h>
#define N 200000
#define N_ (1 << 19) /* N_ = pow2(ceil(log2(N * 2 + 5))) */
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int aa[N], ii[N];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = aa[ii[j]] != aa[i_] ? aa[ii[j]] - aa[i_] : ii[j] - i_;
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
long long st1[N_ * 2], st2[N_ * 2]; int sz[N_ * 2], lz[N_], h_, n_;
void build(int n) {
int i;
h_ = 0;
while (1 << h_ <= n)
h_++;
n_ = 1 << h_;
for (i = 0; i < n_; i++)
sz[n_ + i] = 1;
for (i = n_ - 1; i > 0; i--)
sz[i] = sz[i << 1 | 0] + sz[i << 1 | 1];
}
void put(int i, int x) {
st1[i] += (long long) x * sz[i], st2[i] += (long long) x * sz[i] * (sz[i] + 1) / 2;
if (i < n_)
lz[i] += x;
}
void pus(int i) {
if (lz[i])
put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0;
}
void pul(int i) {
if (!lz[i]) {
int l = i << 1, r = l | 1;
st1[i] = st1[l] + st1[r], st2[i] = st2[l] + st1[l] * sz[r] + st2[r];
}
}
void push(int i) {
int h;
for (h = h_; h > 0; h--)
pus(i >> h);
}
void pull(int i) {
while (i > 1)
pul(i >>= 1);
}
void update(int l, int r, int x) {
int l_ = l += n_, r_ = r += n_;
push(l_), push(r_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
put(l++, x);
if ((r & 1) == 0)
put(r--, x);
}
pull(l_), pull(r_);
}
long long query(int r) {
int l, s;
long long x;
l = 0;
push(l += n_), push(r += n_);
x = 0, s = 0;
for (; l <= r; l >>= 1, r >>= 1)
if ((r & 1) == 0)
x += st2[r] + st1[r] * s, s += sz[r], r--;
return x;
}
int main() {
int n, h, i, i_, j, j_, k, d;
long long ans;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &aa[i]);
ii[i] = i;
}
sort(ii, 0, n);
ans = 0;
build(n * 2 + 4);
for (i = 0; i < n; i = j) {
j = i + 1;
while (j < n && aa[ii[j]] == aa[ii[i]])
j++;
d = n + 2;
update(d, d, 1);
for (i_ = -1, h = i; h <= j; h++) {
j_ = h == j ? n : ii[h], k = j_ - i_ - 1;
if (k > 0) {
ans += query(d - 2) - query(d - k - 2);
update(d - k, d - 1, 1);
d -= k;
}
if (h < j) {
d++;
ans += query(d - 1) - query(d - 2);
update(d, d, 1);
i_ = ii[h];
}
}
d = n + 2, update(d, d, -1);
for (i_ = -1, h = i; h <= j; h++) {
j_ = h == j ? n : ii[h], k = j_ - i_ - 1;
if (k > 0) {
update(d - k, d - 1, -1);
d -= k;
}
if (h < j) {
d++;
update(d, d, -1);
i_ = ii[h];
}
}
}
printf("%lld\n", ans);
return 0;
}
