#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

const int ALPHA = 64;
const int BETA = 100;

const int M = 5000;
const int BIAS = (M / 2);

int cnt[M + 1];

ll calc(const vector<int>& p, int alpha, int beta) {
    ll ans = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        int f = ((n - 1) / 2) - p[i];
        f = max(1, abs(f) - beta);

        int l = max(((n + f - 1) / f) * alpha, beta);
        int L = max(0, i - l);
        int R = min(n - 1, i + l);

        memset(cnt + BIAS - min(l + 1, BIAS), 0, 2 * min(l + 1, BIAS) * sizeof(int));

        int bal = BIAS;
        for (int j = i - 1; j >= L - 1; j--) {
            cnt[bal]++;
            if (j == L - 1) {
                break;
            }
            if (p[j] < p[i]) {
                bal++;
            } else {
                bal--;
            }
        }

        ll cur = 0;

        bal = BIAS;
        for (int j = i + 1; j <= R + 1; j++) {
            cur += (ll)cnt[bal];
            cur += (ll)cnt[bal - 1];

            if (j == R + 1) {
                break;
            }
            if (p[j] < p[i]) {
                bal--;
            } else {
                bal++;
            }
        }

        ans += cur * (p[i] + 1);
    }

    return ans;
}

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    cout << calc(p, ALPHA, BETA) << "\n";
}

void test(int n) {
    mt19937 rnd(239);
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    for (int it = 0; it < 10; it++) {
        shuffle(p.begin(), p.end(), rnd);
        for (int k = 0; k <= 10; k++) {
            double start = TIME;
            cout << k << " " << calc(p, (1 << k), 100) << "\n";
            cout << TIME - start << "\n";
        }
        cout << "___\n";
    }
}

void once(int n) {
    mt19937 rnd(239);
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    shuffle(p.begin(), p.end(), rnd);
    cout << calc(p, ALPHA, BETA) << "\n";
}

int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    once(300'000);

    cerr << TIME << "\n";

    return 0;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}