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

int main(){
    int N;
    cin >> N;
    vector<int> p(N+1);
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        p[n] = i+1;
    }
    multiset<long int> num;
    long int ans = 0;
    num.insert(0);
    num.insert(0);
    num.insert(p[N]);
    num.insert(N+1);
    num.insert(N+1);
    for (int i = N-1; i >= 1; i--) {
        auto lb = num.lower_bound(p[i]);
        long int u = *lb;
        lb++;
        long int v = *lb;
        lb--; lb--;
        long int t = *lb;
        lb--;
        long int s = *lb;
        ans += i * ((t-s) * (u - p[i]) + (v-u) * (p[i] - t));
        num.insert(p[i]);
    }
    cout << ans << endl;
}