#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> p(n), q(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        q[p[i]] = i;
    }
    lint ret        = 0;
    multiset<int> s = {-1, -1, n, n};
    for (int i = n; i >= 1; --i) {
        lint curr = q[i];
        auto it   = prev(s.lower_bound(curr), 2);
        lint ll   = *it;
        lint lr   = *next(it);
        lint rl   = *next(it, 2);
        lint rr   = *next(it, 3);
        ret += ((rr - rl) * (curr - lr) + (lr - ll) * (rl - curr)) * i;
        s.insert(curr);
    }
    cout << ret << "\n";
    return 0;
}