#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 = 128;
const int BETA = 2048;

const int M = 1e4;
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);
        if (i <= 1.5 * beta) {
            l *= 2;
        }
        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 (bal < 0 || bal > BIAS * 2) {
                break;
            }
            if (j == L - 1) {
                break;
            }
            bal += 2 * (p[j] < p[i]) - 1;
        }

        ll cur = 0;

        bal = BIAS;
        for (int j = i + 1; j <= R + 1; j++) {
            cur += cnt[bal];
            cur += cnt[bal - 1];
            if (bal < 0 || bal > BIAS * 2) {
                break;
            }

            if (j == R + 1) {
                break;
            }
            bal += 2 * (p[j] > p[i]) - 1;
        }

        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);
    double start = TIME;
    cout << calc(p, ALPHA, BETA) << "\n";
    cout << TIME - start << "\n";
}

void stress(int n) {
    mt19937 rnd(239);
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    for (int it = 0; it < 1000; it++) {
        shuffle(p.begin(), p.end(), rnd);

        ll val_slow = calc(p, 1024, 512);
        ll val_fast = calc(p, ALPHA, BETA);
        if (val_fast != val_slow) {
            cout << "WA: " << val_fast << " " << val_slow << "\n";
        } else {
            cout << it << " OK\n";
        }
    }
}

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

    once(300'000);
    //stress(300'000);
    return 0;

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

    return 0;
}