#include <bits/stdc++.h>
#define int long long
constexpr int N = 150'0005;
int n, a[N], b[N], c1[N], c2[N], c3[N], ans, B, op;
std::vector<int> p[N];
int sum(int x)
{
    int an = 0;

    for (int i = x; i; i -= i & -i)
        an += c1[i] * (x + 2) * (x + 1) - c2[i] * (2 * x + 3) + c3[i];

    return an / 2;
}
void add(int x, int v)
{
    for (int i = x ; i <= B + n; i += i & -i)
        c1[i] += v,
                 c2[i] += v * x,
                          c3[i] += v * x * x;
}
signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
    std::cin >> n;

    for (int i = 1; i <= n; i++)
    {
        std::cin >> a[i];
		b[i] = a[i];
    }

	std::sort(b + 1, b + n + 1);
	int m = std::unique(b + 1, b + n + 1) - (b + 1);
	for (int i = 1; i <= n; ++i) {
		a[i] = std::lower_bound(b + 1, b + n + 1, a[i]) - b - 1;
        p[a[i]].push_back(i);
	}
    B = n + 1;

    for (int i = 0; i < n; i++)
    {
        p[i].push_back(n + 1);

        for (int j = 0, lst = 0; j < (int)p[i].size(); j++)
        {
            int y = 2 * j - lst + B, x = 2 * j - (p[i][j] - 1) + B;
            ans += sum(y - 1) - (x >= 3 ? sum(x - 2) : 0);
            add(x, 1), add(y + 1, -1);
            lst = p[i][j];
        }

        for (int j = 0, lst = 0; j < (int)p[i].size(); j++)
        {
            int y = 2 * j - lst + B, x = 2 * j - (p[i][j] - 1) + B;
            add(x, -1), add(y + 1, 1);
            lst = p[i][j];
        }
    }

    std::cout << ans;
}