#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 = 1e6 + 10, mod = 1e9+7;
static long long bit[2][2*mx];
int a[mx];
int n, base = 1e6+1;
vector<int> positions[mx], compress;
map<int, int> mp;
//map<int, vector<int> > positions;
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 num)
{
long long ret = 0;
vector< pair<int, int> > moves;
positions[num].push_back(n+1);
int end = base, start = end - (positions[num][0]-1);
update(start, end, 1);
moves.push_back(make_pair(start, end));
rep(i, 0, positions[num].size()-2)
{
int end = 2*(i+1) - positions[num][i] + base-1;
int start = end - (positions[num][i+1]-positions[num][i]-1);
long long get = 0;
int idx = end;
do
{
get = query(idx);
ret += get;
idx--;
} while(get > 0 and idx >= start);
update(start+1, end+1, 1);
moves.push_back(make_pair(start+1, end+1));
}
rep(i, 0, moves.size()-1)
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<=1e6);
rep(i, 1, n)
{
cin >> a[i];
assert(0 < a[i] and a[i] <= 1e9);
compress.push_back(a[i]);
//positions[a[i]].push_back(i);
}
sort(compress.begin(), compress.end());
compress.erase(unique(compress.begin(), compress.end()), compress.end());
rep(i, 0, compress.size()-1)
mp[compress[i]] = i;
rep(i, 1, n)
positions[mp[a[i]]].push_back(i);
long long ans = 0;
//map<int, vector<int> >::iterator it = positions.begin();
//for(; it!=positions.end(); ++it)
// ans += process(it->first);
for(int i = 0; i<mx; ++i)
if(positions[i].size())
ans += process(i);
cout << ans << '\n';
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8Y2Fzc2VydD4KI2RlZmluZSByZiBmcmVvcGVuKCJpbi5pbiIsICJyIiwgc3RkaW4pCiNkZWZpbmUgd2YgZnJlb3Blbigib3V0Lm91dCIsICJ3Iiwgc3Rkb3V0KQojZGVmaW5lIHJlcChpLCBzLCBuKSBmb3IoaW50IGk9aW50KHMpOyBpPD1pbnQobik7ICsraSkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgaW50IG14ID0gMWU2ICsgMTAsIG1vZCA9IDFlOSs3OwogCnN0YXRpYyBsb25nIGxvbmcgYml0WzJdWzIqbXhdOwppbnQgYVtteF07CmludCBuLCBiYXNlID0gMWU2KzE7CnZlY3RvcjxpbnQ+IHBvc2l0aW9uc1tteF0sIGNvbXByZXNzOwptYXA8aW50LCBpbnQ+IG1wOwovL21hcDxpbnQsIHZlY3RvcjxpbnQ+ID4gcG9zaXRpb25zOwogCmlubGluZSB2b2lkIHVwKGxvbmcgbG9uZyBiaXRbXSwgaW50IGksIGxvbmcgbG9uZyB2KQp7Cglmb3IgKDsgaTwyKm14OyBpKz1pJi1pKQoJCWJpdFtpXSArPSB2Owp9CiAKaW5saW5lIGxvbmcgbG9uZyBxdShsb25nIGxvbmcgYml0W10sIGludCBpKQp7Cglsb25nIGxvbmcgcmV0ID0gMDsKCWZvciAoOyBpOyBpLT1pJi1pKQoJCXJldCArPSBiaXRbaV07CglyZXR1cm4gcmV0Owp9CiAKaW5saW5lIHZvaWQgdXBkYXRlKGludCBzLCBpbnQgZSwgaW50IGMpCnsKCXVwKGJpdFswXSwgcywgYyk7IHVwKGJpdFswXSwgZSsxLCAtYyk7Cgl1cChiaXRbMV0sIHMsIGMqKDEtcykpOyB1cChiaXRbMV0sIGUrMSwgYyplKTsKfQogCmlubGluZSBsb25nIGxvbmcgcXVlcnkoaW50IGkpCnsKCXJldHVybiBxdShiaXRbMF0sIGkpKmkgKyBxdShiaXRbMV0sIGkpOwp9CiAKbG9uZyBsb25nIHByb2Nlc3MoaW50IG51bSkKewoJbG9uZyBsb25nIHJldCA9IDA7Cgl2ZWN0b3I8IHBhaXI8aW50LCBpbnQ+ID4gbW92ZXM7CgkKCXBvc2l0aW9uc1tudW1dLnB1c2hfYmFjayhuKzEpOwoJaW50IGVuZCA9IGJhc2UsIHN0YXJ0ID0gZW5kIC0gKHBvc2l0aW9uc1tudW1dWzBdLTEpOwogCgl1cGRhdGUoc3RhcnQsIGVuZCwgMSk7Cgltb3Zlcy5wdXNoX2JhY2sobWFrZV9wYWlyKHN0YXJ0LCBlbmQpKTsKIAoJcmVwKGksIDAsIHBvc2l0aW9uc1tudW1dLnNpemUoKS0yKQoJewoJCWludCBlbmQgPSAyKihpKzEpIC0gcG9zaXRpb25zW251bV1baV0gKyBiYXNlLTE7CgkJaW50IHN0YXJ0ID0gZW5kIC0gKHBvc2l0aW9uc1tudW1dW2krMV0tcG9zaXRpb25zW251bV1baV0tMSk7CiAKCQlsb25nIGxvbmcgZ2V0ID0gMDsKCQlpbnQgaWR4ID0gZW5kOwoJCWRvCgkJewoJCQlnZXQgPSBxdWVyeShpZHgpOwoJCQlyZXQgKz0gZ2V0OwoJCQlpZHgtLTsKCQl9IHdoaWxlKGdldCA+IDAgYW5kIGlkeCA+PSBzdGFydCk7CgkJCgkJdXBkYXRlKHN0YXJ0KzEsIGVuZCsxLCAxKTsKCQltb3Zlcy5wdXNoX2JhY2sobWFrZV9wYWlyKHN0YXJ0KzEsIGVuZCsxKSk7Cgl9CiAKCXJlcChpLCAwLCBtb3Zlcy5zaXplKCktMSkKCQl1cGRhdGUobW92ZXNbaV0uZmlyc3QsIG1vdmVzW2ldLnNlY29uZCwgLTEpOwogCglyZXR1cm4gcmV0Owp9CiAKaW50IG1haW4oKQp7CgkvL3JmOy8vIHdmOwoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAKCWNpbiA+PiBuOwoJYXNzZXJ0KDAgPCBuIGFuZCBuPD0xZTYpOwoJcmVwKGksIDEsIG4pCgl7CgkJY2luID4+IGFbaV07CgkJYXNzZXJ0KDAgPCBhW2ldIGFuZCBhW2ldIDw9IDFlOSk7CgkJY29tcHJlc3MucHVzaF9iYWNrKGFbaV0pOwoJCS8vcG9zaXRpb25zW2FbaV1dLnB1c2hfYmFjayhpKTsKCX0KCXNvcnQoY29tcHJlc3MuYmVnaW4oKSwgY29tcHJlc3MuZW5kKCkpOwoJY29tcHJlc3MuZXJhc2UodW5pcXVlKGNvbXByZXNzLmJlZ2luKCksIGNvbXByZXNzLmVuZCgpKSwgY29tcHJlc3MuZW5kKCkpOwogCglyZXAoaSwgMCwgY29tcHJlc3Muc2l6ZSgpLTEpCgkJbXBbY29tcHJlc3NbaV1dID0gaTsKCXJlcChpLCAxLCBuKQoJCXBvc2l0aW9uc1ttcFthW2ldXV0ucHVzaF9iYWNrKGkpOwogCglsb25nIGxvbmcgYW5zID0gMDsKCS8vbWFwPGludCwgdmVjdG9yPGludD4gPjo6aXRlcmF0b3IgaXQgPSBwb3NpdGlvbnMuYmVnaW4oKTsKCS8vZm9yKDsgaXQhPXBvc2l0aW9ucy5lbmQoKTsgKytpdCkKCS8vCWFucyArPSBwcm9jZXNzKGl0LT5maXJzdCk7Cglmb3IoaW50IGkgPSAwOyBpPG14OyArK2kpCgkJaWYocG9zaXRpb25zW2ldLnNpemUoKSkKCQkJYW5zICs9IHByb2Nlc3MoaSk7CiAKCWNvdXQgPDwgYW5zIDw8ICdcbic7CgkKCXJldHVybiAwOwp9CiA=