#include "bits/stdc++.h"

using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<int> xs(n + 1);
    for (int i = 0; i < n; i++)
    {
        int p;
        cin >> p;
        xs[p] = i + 1;
    }
    multiset<int> id;
    id.insert(0);
    id.insert(0);
    id.insert(n + 1);
    id.insert(n + 1);
    long ans = 0;
    for (int p = n; p > 0; p--)
    {
        id.insert(xs[p]);
        auto it = id.find(xs[p]);
        auto itne = next(it);
        auto itpr = prev(it);
        long res = 0;
        res += 1L * (*itpr - *prev(itpr)) * (*itne - xs[p]);
        res += 1L * (xs[p] - *itpr) * (*next(itne) - *itne);
        //cout << res << endl;
        res *= p;
        ans += res;
    }
    cout << ans << endl;
}

int main()
{
    solve();
    return 0;
}