#include<bits/stdc++.h>
#define rg register
#define il inline
#define ll long long
using namespace std;

const int INF = 0x7ffffff / 2, N = 100005;
ll ans[N << 3], res;
ll tag1[N << 3], tag2[N << 3];
int n, a[N];
vector<int> b[N];

il int rd(){
	char c = getchar(); 
	int n = 0;
	while (c < '0' || c > '9'){ 
		c = getchar(); 
	}
	while (c >= '0' && c <= '9'){ 
		n = (n << 1) + (n << 3) + (c & 15); 
		c = getchar(); 
	}
	return n;
}

il void pushup(int k){
	ans[k] = ans[k << 1] + ans[k << 1 | 1];
}

void modify(int k, ll v, ll d, int len){
	ans[k] += (v * 2 + (len - 1) * d) * len / 2;
	tag1[k] += v;
	tag2[k] += d;
}

void pushdown(int k, int len1, int len2){
	if (tag1[k] || tag2[k]){
		modify(k << 1, tag1[k], tag2[k], len1);
		modify(k << 1 | 1, tag1[k] + tag2[k] * len1, tag2[k], len2);
		tag1[k] = tag2[k] = 0;
	}
}

il void change(int k, int l, int r, int x, int y, int v, int d){
	if (l >= x && r <= y){
		modify(k, v + (l - x) * d, d, r - l + 1);
		return;
	}
	int mid = l + r >> 1;
	pushdown(k, mid - l + 1, r - mid);
	if (x <= mid) change(k << 1, l, mid, x, y, v, d);
	if (y >= mid + 1) change(k << 1 | 1, mid + 1, r, x, y, v, d);
	pushup(k);
}

il ll ask(int k, int l, int r, int x, int y){
	if (l >= x && r <= y) return ans[k];
	int mid = l + r >> 1;
	pushdown(k, mid - l + 1, r - mid);
	ll res = 0;
	if (x <= mid) res += ask(k << 1, l, mid, x, y);
	if (y >= mid + 1) res += ask(k << 1 | 1, mid + 1, r, x, y);
	return res;
}

signed main(){
	n = rd();
	for (int i = 1; i <= n; i++){
		a[i] = rd();
		b[a[i]].push_back(i);
	}
	int det = n + 1;
	for (int i = 0; i < n; i++){
		b[i].push_back(n + 1);
		int last = 0;
		for (int j = 0; j < b[i].size(); j++){
			int x = 2 * j - (b[i][j] - 1) + det, y = 2 * j - last + det;
			res += ask(1, 1, 2 * n + 1, max(x - 1, 1), y - 1);
			change(1, 1, 2 * n + 1, x, y, 1, 1);
			if (x + 1 <= 2 * n + 1) change(1, 1, 2 * n + 1, y + 1, 2 * n + 1, y - x + 1, 0);
			last = b[i][j];
		}
		last = 0;
		for (int j = 0; j < b[i].size(); j++){
			int x = 2 * j - (b[i][j] - 1) + det, y = 2 * j - last + det;
			change(1, 1, 2 * n + 1, x, y, -1, -1);
			if (x + 1 <= 2 * n + 1) change(1, 1, 2 * n + 1, y + 1, 2 * n + 1, -(y - x + 1), 0);
			last = b[i][j];
		}
	}
	cout << res;
	return 0;
}