#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SparseTable {
    vector<vector<long long>> table_min;
    vector<vector<long long>> table_max;
    vector<long long> log_table;
    SparseTable(const vector<long long>& A) : table_min(), table_max() {
        log_table.resize(A.size() + 1);
        log_table[1] = 0;
        for (long long i = 2; i <= A.size(); i++) {
            log_table[i] = log_table[i / 2] + 1;
        }
        table_min.resize(A.size());
        fill(table_min.begin(), table_min.end(), vector<long long>(log_table[A.size()] + 1));
        for (long long i = 0; i < A.size(); i++) table_min[i][0] = A[i];
        for (long long i = 1; (1 << i) <= A.size(); i++) {
            for (long long j = 0; j + (1 << i) <= A.size(); j++) {
                table_min[j][i] = min(table_min[j][i - 1], table_min[j + (1 << (i - 1))][i - 1]);
            }
        }
        table_max.resize(A.size());
        fill(table_max.begin(), table_max.end(), vector<long long>(log_table[A.size()] + 1));
        for (long long i = 0; i < A.size(); i++) table_max[i][0] = A[i];
        for (long long i = 1; (1 << i) <= A.size(); i++) {
            for (long long j = 0; j + (1 << i) <= A.size(); j++) {
                table_max[j][i] = max(table_max[j][i - 1], table_max[j + (1 << (i - 1))][i - 1]);
            }
        }
    }
    long long query_min(long long i, long long j) {
        return min(table_min[i][log_table[j - i + 1]], table_min[j - (1 << log_table[j - i + 1]) + 1][log_table[j - i + 1]]);
    }
    long long query_max(long long i, long long j) {
        return max(table_max[i][log_table[j - i + 1]], table_max[j - (1 << log_table[j - i + 1]) + 1][log_table[j - i + 1]]);
    }
};

ll left(const ll N, const ll& i, const ll& border, const vector<ll>& P, SparseTable& st) {
    if (i <= 0) return -1;
    if (st.query_max(0, i - 1) <= border) return -1;
    ll imax = i;
    ll imin = 0;
    while (imax - imin > 1) {
        ll imid = (imax + imin) / 2;
        if (st.query_max(imid, i - 1) > border) {
            imin = imid;
        } else {
            imax = imid;
        }
    }
    return imin;
}

ll right(const ll N, const ll& i, const ll& border, const vector<ll>& P, SparseTable& st) {
    if (N - 1 <= i) return N;
    if (st.query_max(i + 1, N - 1) <= border) return N;
    ll imax = N;
    ll imin = i;
    while (imax - imin > 1) {
        ll imid = (imax + imin) / 2;
        if (st.query_max(i + 1, imid) > border) {
            imax = imid;
        } else {
            imin = imid;
        }
    }
    return imax;
}

int main() {
    int N;
    cin >> N;
    vector<ll> P(N);
    for (size_t i = 0; i < N; i++) {
        cin >> P[i];
    }
    SparseTable st(P);
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ll left1 = left(N, i, P[i], P, st);
        ll left2 = left(N, left1, P[i], P, st);
        ll right1 = right(N, i, P[i], P, st);
        ll right2 = right(N, right1, P[i], P, st);
        if (i + 1 < N)
            if (st.query_max(i + 1, N - 1) > P[i]) ans += (right2 - right1) * (i - left1) * P[i];
        if (0 <= i - 1)
            if (st.query_max(0, i - 1) > P[i]) ans += (right1 - i) * (left1 - left2) * P[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 34688