#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;
}