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

#define int long long
#define rep(i, a, b) for (int i = a; i < b; i++)

signed main() {
    int N;
    cin >> N;

    vector<int> P(N);
    rep(i, 0, N) cin >> P[i];

    vector<int> Index(N+1);
    rep(i, 0, N) Index[P[i]] = i;

    multiset<int> S;
    S.insert(-1);
    S.insert(-1);
    S.insert(N);
    S.insert(N);

    int ans = 0;

    for (int p = N; p > 0; p--) {
        int i = Index[p];
        auto pos = S.lower_bound(i);

        pos++;
        int d = *pos;

        pos--;
        int c = *pos;

        pos--;
        int b = *pos;

        pos--;
        int a = *pos;

        int cp = (i - b) * (d - c) + (c - i) * (b - a);
        ans += cp * p;

        S.insert(i);
    }

    cout << ans << endl;
}