#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using ll = long long int;
using namespace std;

int main(){
    int n; cin >> n;
    vector<int> idx(n, 0);
    for(int i=0; i<n; i++){
        int val; cin >> val; val--;
        idx[val] = i;
    }
    reverse(idx.begin(), idx.end());
    multiset<int> ms{-1,-1,n,n};
    ll ans = 0;
    for(ll i=0; i<n; i++){
        if(i == 0){ms.insert(idx[i]); continue;}
        auto it = ms.lower_bound(idx[i]);
        ll R2 = *++it;
        ll R1 = *--it;
        ll L1 = *--it;
        ll L2 = *--it;
        ans += (L1 - L2) * (R1 - idx[i]) * (n-i);
        ans += (R2 - R1) * (idx[i] - L1) * (n-i);
        ms.insert(idx[i]);
    }
    cout << ans << endl;
    return 0;
}