#include <bits/stdc++.h>
using namespace std;
int main() {
    freopen("in", "r", stdin);
    freopen("err", "w", stderr);
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n; vector<int> a(n + 1), p(n + 1);
    for(int i = 1; i <= n; ++i) cin >> a[i], p[a[i]] = i;
    long long ans = 0; vector<int> buf(2 * n + 3);
    const auto c = buf.begin() + n + 1;
    for(int i = 1; i <= n; ++i) {
        const double t = abs(0.5 - 1.0 * (i - 1) / (n - 1));
        const int lim = max<int>(4 / max(t * t, 1e-6), 30);
        const int w = p[i], L = max(1, w - lim), R = min(n, w + lim);
        long long tmp = 0; int l = 0, r = 0;
        for(int q = w, y = 0; q >= L; --q)
            ++c[y += a[q] > i ? 1 : -1];
        for(int q = w, y = 1; q <= R; ++q)
            y += a[q] > i ? 1 : -1, tmp += c[-y] + c[-y - 1];
        while(c[l - 1]) --l; while(c[r]) ++r;
        fill(c + l, c + r, 0), ans += tmp * i;
    }
    printf("%lld\n", ans);
}