#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <cassert>
#define rf freopen("in.in", "r", stdin)
#define wf freopen("out.out", "w", stdout)
#define rep(i, s, n) for(int i=int(s); i<=int(n); ++i)
using namespace std;
const int mx = 5e5 + 10, mod = 1e9+7;
static long long bit[2][2*mx];
int a[mx];
int n, base = 5e5+1;
pair<int, int> num_pos[mx], moves[mx];
inline void up(long long bit[], int i, long long v)
{
for (; i<2*mx; i+=i&-i)
bit[i] += v;
}
inline long long qu(long long bit[], int i)
{
long long ret = 0;
for (; i; i-=i&-i)
ret += bit[i];
return ret;
}
inline void update(int s, int e, int c)
{
up(bit[0], s, c); up(bit[0], e+1, -c);
up(bit[1], s, c*(1-s)); up(bit[1], e+1, c*e);
}
inline long long query(int i)
{
return qu(bit[0], i)*i + qu(bit[1], i);
}
long long process(int &idx)
{
long long ret = 0;
int moves_idx = 0;
int end = base, start = end - (num_pos[idx].second-1), range_start = idx;
update(start, end, 1);
moves[++moves_idx] = make_pair(start, end);
while(num_pos[idx].first == num_pos[range_start].first)
{
int end = 2*(idx-range_start+1) - num_pos[idx].second + base-1;
int nextid = (num_pos[idx].first != num_pos[idx+1].first)? n+1: num_pos[idx+1].second;
int start = end - (nextid - num_pos[idx].second-1);
idx++;
long long get = 0;
int iter = end;
do
{
get = query(iter);
ret += get;
iter--;
} while(get > 0 and iter >= start);
update(start+1, end+1, 1);
moves[++moves_idx] = make_pair(start+1, end+1);
}
rep(i, 1, moves_idx)
update(moves[i].first, moves[i].second, -1);
return ret;
}
int main()
{
//rf;// wf;
ios::sync_with_stdio(0);
cin >> n;
assert(0 < n and n<=5e5);
rep(i, 1, n)
{
cin >> a[i];
assert(0 < a[i] and a[i] <= 1e9);
num_pos[i] = make_pair(a[i], i);
}
sort(num_pos+1, num_pos+n+1);
long long ans = 0;
int idx = 1;
while(idx <= n)
ans += process(idx);
cout << ans << '\n';
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8Y2Fzc2VydD4KI2RlZmluZSByZiBmcmVvcGVuKCJpbi5pbiIsICJyIiwgc3RkaW4pCiNkZWZpbmUgd2YgZnJlb3Blbigib3V0Lm91dCIsICJ3Iiwgc3Rkb3V0KQojZGVmaW5lIHJlcChpLCBzLCBuKSBmb3IoaW50IGk9aW50KHMpOyBpPD1pbnQobik7ICsraSkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgaW50IG14ID0gNWU1ICsgMTAsIG1vZCA9IDFlOSs3OwoKc3RhdGljIGxvbmcgbG9uZyBiaXRbMl1bMipteF07CmludCBhW214XTsKaW50IG4sIGJhc2UgPSA1ZTUrMTsKcGFpcjxpbnQsIGludD4gbnVtX3Bvc1tteF0sIG1vdmVzW214XTsKCmlubGluZSB2b2lkIHVwKGxvbmcgbG9uZyBiaXRbXSwgaW50IGksIGxvbmcgbG9uZyB2KQp7Cglmb3IgKDsgaTwyKm14OyBpKz1pJi1pKQoJCWJpdFtpXSArPSB2Owp9CgppbmxpbmUgbG9uZyBsb25nIHF1KGxvbmcgbG9uZyBiaXRbXSwgaW50IGkpCnsKCWxvbmcgbG9uZyByZXQgPSAwOwoJZm9yICg7IGk7IGktPWkmLWkpCgkJcmV0ICs9IGJpdFtpXTsKCXJldHVybiByZXQ7Cn0KCmlubGluZSB2b2lkIHVwZGF0ZShpbnQgcywgaW50IGUsIGludCBjKQp7Cgl1cChiaXRbMF0sIHMsIGMpOyB1cChiaXRbMF0sIGUrMSwgLWMpOwoJdXAoYml0WzFdLCBzLCBjKigxLXMpKTsgdXAoYml0WzFdLCBlKzEsIGMqZSk7Cn0KCmlubGluZSBsb25nIGxvbmcgcXVlcnkoaW50IGkpCnsKCXJldHVybiBxdShiaXRbMF0sIGkpKmkgKyBxdShiaXRbMV0sIGkpOwp9Cgpsb25nIGxvbmcgcHJvY2VzcyhpbnQgJmlkeCkKewoJbG9uZyBsb25nIHJldCA9IDA7CglpbnQgbW92ZXNfaWR4ID0gMDsKCQoJaW50IGVuZCA9IGJhc2UsIHN0YXJ0ID0gZW5kIC0gKG51bV9wb3NbaWR4XS5zZWNvbmQtMSksIHJhbmdlX3N0YXJ0ID0gaWR4OwoKCXVwZGF0ZShzdGFydCwgZW5kLCAxKTsKCW1vdmVzWysrbW92ZXNfaWR4XSA9IG1ha2VfcGFpcihzdGFydCwgZW5kKTsKCgl3aGlsZShudW1fcG9zW2lkeF0uZmlyc3QgPT0gbnVtX3Bvc1tyYW5nZV9zdGFydF0uZmlyc3QpCgl7CgkJaW50IGVuZCA9IDIqKGlkeC1yYW5nZV9zdGFydCsxKSAtIG51bV9wb3NbaWR4XS5zZWNvbmQgKyBiYXNlLTE7CgkJaW50IG5leHRpZCA9IChudW1fcG9zW2lkeF0uZmlyc3QgIT0gbnVtX3Bvc1tpZHgrMV0uZmlyc3QpPyBuKzE6IG51bV9wb3NbaWR4KzFdLnNlY29uZDsKCQlpbnQgc3RhcnQgPSBlbmQgLSAobmV4dGlkIC0gbnVtX3Bvc1tpZHhdLnNlY29uZC0xKTsKCQlpZHgrKzsKCgkJbG9uZyBsb25nIGdldCA9IDA7CgkJaW50IGl0ZXIgPSBlbmQ7CgkJZG8KCQl7CgkJCWdldCA9IHF1ZXJ5KGl0ZXIpOwoJCQlyZXQgKz0gZ2V0OwoJCQlpdGVyLS07CgkJfSB3aGlsZShnZXQgPiAwIGFuZCBpdGVyID49IHN0YXJ0KTsKCQkKCQl1cGRhdGUoc3RhcnQrMSwgZW5kKzEsIDEpOwoJCW1vdmVzWysrbW92ZXNfaWR4XSA9IG1ha2VfcGFpcihzdGFydCsxLCBlbmQrMSk7Cgl9CgoJcmVwKGksIDEsIG1vdmVzX2lkeCkKCQl1cGRhdGUobW92ZXNbaV0uZmlyc3QsIG1vdmVzW2ldLnNlY29uZCwgLTEpOwoKCXJldHVybiByZXQ7Cn0KCmludCBtYWluKCkKewoJLy9yZjsvLyB3ZjsKCWlvczo6c3luY193aXRoX3N0ZGlvKDApOwoKCWNpbiA+PiBuOwoJYXNzZXJ0KDAgPCBuIGFuZCBuPD01ZTUpOwoJcmVwKGksIDEsIG4pCgl7CgkJY2luID4+IGFbaV07CgkJYXNzZXJ0KDAgPCBhW2ldIGFuZCBhW2ldIDw9IDFlOSk7CgkJCgkJbnVtX3Bvc1tpXSA9IG1ha2VfcGFpcihhW2ldLCBpKTsKCX0KCglzb3J0KG51bV9wb3MrMSwgbnVtX3BvcytuKzEpOwoKCWxvbmcgbG9uZyBhbnMgPSAwOwoJaW50IGlkeCA9IDE7Cgl3aGlsZShpZHggPD0gbikKCQlhbnMgKz0gcHJvY2VzcyhpZHgpOwoKCWNvdXQgPDwgYW5zIDw8ICdcbic7CgkKCXJldHVybiAwOwp9Cg==