#include using namespace std; const int kN = 100'000 + 5; const int kM = kN + kN; long long st[kM * 4], cf[kM * 4], ct[kM * 4]; int a[kN], l[kN], r[kN]; bool cl[kM * 4]; vector pos[kN]; void Apply(int o, long long f, long long t, bool c, int l, int r) { if (c) { cf[o] = ct[o] = st[o] = 0; cl[o] = true; } cf[o] += f; ct[o] += t; st[o] += f * (l + r - 1) * (r - l) / 2; st[o] += t * (r - l); } void Push(int o, int l, int r) { int m = (l + r) >> 1; Apply(o * 2 + 1, cf[o], ct[o], cl[o], l, m); Apply(o * 2 + 2, cf[o], ct[o], cl[o], m, r); cf[o] = 0; ct[o] = 0; cl[o] = false; } long long Query(int l, int r, int ql, int qr, int o = 0) { if (l >= qr || ql >= r) return 0; if (l >= ql && r <= qr) return st[o]; Push(o, l, r); int m = (l + r) >> 1; return Query(l, m, ql, qr, o * 2 + 1) + Query(m, r, ql, qr, o * 2 + 2); } void Modify(int l, int r, int ql, int qr, long long f, long long t, int o = 0) { if (l >= qr || ql >= r) return; if (l >= ql && r <= qr) return Apply(o, f, t, false, l, r); Push(o, l, r); int m = (l + r) >> 1; Modify(l, m, ql, qr, f, t, o * 2 + 1); Modify(m, r, ql, qr, f, t, o * 2 + 2); st[o] = st[o * 2 + 1] + st[o * 2 + 2]; } void Clear(int o) { st[o] = cf[o] = ct[o] = 0; cl[o] = true; } long long Solve(int v, int n) { int m = pos[v].size(); for (int i = 0; i < m; ++i) { r[i] = pos[v][i] - 1; l[i + 1] = pos[v][i]; } r[m] = n; long long res = 0; for (int i = 0; i <= m; ++i) { int ql = 2 * i - r[i] + kN, qr = 2 * i - l[i] + kN; res += Query(0, kM, ql - 1, qr); Modify(0, kM, qr + 1, kM, 0, qr - ql + 1); Modify(0, kM, ql, qr + 1, 1, 1 - ql); } Clear(0); return res; } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); pos[a[i]].push_back(i); } long long ans = 0; for (int i = 0; i < kN; ++i) { if (!pos[i].empty()) ans += Solve(i, n); } printf("%lld\n", ans); return 0; }