#include <bits/stdc++.h>
using namespace std;
template <class T> struct Fenwick_Tree {
vector<T> bit_add, bit_sub;
int n;
Fenwick_Tree(int n = 0) : n(n), bit_add(n + 1), bit_sub(n + 1) {}
void clear() {
fill(bit_add.begin(), bit_add.end(), T(0));
fill(bit_sub.begin(), bit_sub.end(), T(0));
}
void update(int u, int v, T val) {
for (int i = u; i <= n; i += i & -i) {
bit_add[i] += val;
bit_sub[i] += 1LL * (u - 1) * val;
}
for (int i = v; i <= n; i += i & -i) {
bit_add[i] -= val;
bit_sub[i] -= 1LL * v * val;
}
}
void update(int u, T val) { update(u, u, val); }
T get(int u) {
T ans1 = 0, ans2 = 0;
for (int i = u; i; i -= i & -i) {
ans1 += bit_add[i];
ans2 += bit_sub[i];
}
return u * ans1 - ans2;
}
T get(int l, int r) { return get(r) - get(l - 1); }
};
long long def(int x) { return 1LL * x * (x + 1) / 2; }
template <class T>
struct lazy_segment_tree {
#define mid ((l + r) >> 1)
vector <T> it, lazy, start;
int n;
void push(int idx, int l, int r) {
if(lazy[idx] == 0 and start[idx] == 0) return;
it[idx] += lazy[idx] * def(r - l + 1) + start[idx] * (r - l + 1);
if(l != r) {
assert((2 * idx) <= 4 * n and (2 * idx + 1) <= 4 * n);
lazy[idx << 1] += lazy[idx];
lazy[idx << 1 | 1] += lazy[idx];
start[idx << 1] += start[idx];
start[idx << 1 | 1] += start[idx] + (mid - l + 1) * lazy[idx];
}
start[idx] = lazy[idx] = 0;
}
T merge(const T &a, const T &b) {
return a + b;
}
void update(int idx, int l, int r, int u, int v, T val) {
push(idx, l, r);
if(l > v || r < u) return;
if(l >= u && r <= v) {
lazy[idx] += val;
start[idx] += val * (l - u);
push(idx, l, r);
return;
}
update(idx << 1, l, mid, u, v, val);
update(idx << 1 | 1, mid + 1, r, u, v, val);
it[idx] = merge(it[idx << 1], it[idx << 1 | 1]);
}
T get(int idx, int l, int r, int u, int v) {
push(idx, l, r);
if(l > v || r < u) return 0;
if(l >= u && r <= v) return it[idx];
return merge(get(idx << 1, l, mid, u, v), get(idx << 1 | 1, mid + 1, r, u, v));
}
public :
explicit lazy_segment_tree(int n) :
n(n), lazy(n << 2 | 1, 0), it(n << 2 | 1), start(n << 2 | 1) {}
void update(int l, int r, T val) {
update(1, 1, n, l, r, val);
}
T get(int l, int r) {
return get(1, 1, n, l, r);
}
T get(int u) {
return get(u, u);
}
#undef mid
};
const int MAXN = 2e5 + 5;
int n, a[MAXN];
vector <int> pos[MAXN];
void you_make_it(void) {
cin >> n;
for (int i = 1; i <= n; ++i) {
pos[i].push_back(0);
cin >> a[i];
}
vector <int> b(a + 1, a + n + 1);
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (int i = 1; i <= n; ++i) {
a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
pos[a[i]].push_back(i);
}
for (int i = 1; i <= n; ++i) {
pos[i].emplace_back(n + 1);
}
Fenwick_Tree <long long> bit(2 * n + 1);
lazy_segment_tree <long long> it(2 * n + 1);
long long ans = 0;
for (int u = 1; u <= n; ++u) {
for (int i = 0; i < pos[u].size() - 1; ++i) {
int r = 2 * (i + 1) - pos[u][i];
int l = r - (pos[u][i + 1] - pos[u][i] - 1);
ans += it.get(l - 1 + n, r - 1 + n) + bit.get(l - 1 + n, r - 1 + n);
it.update(l + n, r + n, 1);
bit.update(r + n + 1, 2 * n + 1, r - l + 1);
}
for (int i = 0; i < pos[u].size() - 1; ++i) {
int r = 2 * (i + 1) - pos[u][i];
int l = r - (pos[u][i + 1] - pos[u][i] - 1);
it.update(l + n, r + n, - 1);
bit.update(r + n + 1, 2 * n + 1, -r + l - 1);
}
}
cout << ans;
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
you_make_it();
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
