#include <bits/stdc++.h>
using namespace std;
const int N = 200'000 + 10;
int n;
int a[N];
vector<int> pos[N];
namespace IT {
struct Node {
int cnt;
long long value;
Node() : cnt(0), value(0) {}
Node(int cnt, long long value) : cnt(cnt), value(value) {}
} f[N << 2];
long long lazy[N << 2];
Node merge(Node lt, Node rt) {
return {lt.cnt + rt.cnt, lt.value + rt.value};
}
inline long long sum(int l, int r) {
tie(l, r) = make_pair(-r, -l);
return 1ll * (r + l) * (r - l + 1) / 2;
}
void push(int s, int l, int r) {
if (!lazy[s]) return;
int mid = (l + r) >> 1;
f[s << 1].cnt += 1ll * (mid - l + 1) * lazy[s];
f[s << 1].value += sum(l, mid) * lazy[s];
lazy[s << 1] += lazy[s];
f[s << 1 | 1].cnt += 1ll * (r - mid) * lazy[s];
f[s << 1 | 1].value += sum(mid + 1, r) * lazy[s];
lazy[s << 1 | 1] += lazy[s];
lazy[s] = 0;
}
void update(int s, int l, int r, int u, int v, int x) {
if (v < l || u > r) return;
if (u <= l && r <= v) {
f[s].cnt += 1ll * (r - l + 1) * x;
f[s].value += sum(l, r) * x;
lazy[s] += x;
return;
}
push(s, l, r);
int mid = (l + r) >> 1;
update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
f[s] = merge(f[s << 1], f[s << 1 | 1]);
}
Node query(int s, int l, int r, int u, int v) {
if (v < l || u > r) return Node();
if (u <= l && r <= v) return f[s];
push(s, l, r);
int mid = (l + r) >> 1;
return merge(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
}
inline void update(int l, int r, int x) {
update(1, -n, n, l, r, x);
}
inline long long query(int l, int r) {
auto [cnt, value] = query(1, -n, n, l, r);
return value - 1ll * cnt * (-r - 1);
}
}
namespace BIT {
int bit[N];
inline void upd(int i, int x) {
for (; i <= n; i += i & -i) bit[i] += x;
}
inline int que(int i) {
int ret = 0;
for (; i; i -= i & -i) ret += bit[i];
return ret;
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
vector<int> allValue(a + 1, a + n + 1);
{ // compress
sort(allValue.begin(), allValue.end());
allValue.erase(unique(allValue.begin(), allValue.end()), allValue.end());
for (int i = 1; i <= n; ++i)
a[i] = upper_bound(allValue.begin(), allValue.end(), a[i]) - allValue.begin();
}
for (int i = 1; i <= n; ++i) pos[i] = {0};
for (int i = 1; i <= n; ++i) pos[a[i]].push_back(i);
for (int i = 1; i <= n; ++i) pos[i].push_back(n + 1);
long long answer = 0;
IT::update(0, 0, 1);
for (int i = 1; i <= n; ++i) BIT::upd(i, -1);
for (int index = 1; index <= (int)allValue.size(); ++index) {
if (pos[index][1] != 1) { // pre update
int p = pos[index][1];
IT::update(BIT::que(p - 1), BIT::que(1), 1);
}
for (int i = 1; i < (int)pos[index].size() - 1; ++i) {
int cur = pos[index][i], nxt = pos[index][i + 1];
BIT::upd(cur, 2);
int le = BIT::que(nxt - 1), ri = BIT::que(cur);
answer += IT::query(le - 1, ri - 1);
answer += 1ll * IT::query(1, -n, n, -n, le - 2).cnt * (ri - le + 1);
IT::update(le, ri, 1);
}
for (int i = (int)pos[index].size() - 2; i >= 1; --i) {
int cur = pos[index][i], nxt = pos[index][i + 1];
int le = BIT::que(nxt - 1), ri = BIT::que(cur);
IT::update(le, ri, -1);
BIT::upd(cur, -2);
}
if (pos[index][1] != 1) { // pre update
int p = pos[index][1];
IT::update(BIT::que(p - 1), BIT::que(1), -1);
}
}
cout << answer << "\n";
}
