#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    int n;
    cin>>n;
    int pos[n+1];
    for(int i=0;i<n;i++){
        int p;
        cin>>p;
        pos[p]=i+1;
    }
    ll ans=0;
    multiset<int> se;
    se.insert(pos[n]);
    se.insert(0);
    se.insert(n+1);
    se.insert(0);
    se.insert(n+1);
    for(int i=n-1;i>0;i--){
        auto it=se.lower_bound(pos[i]);
        --it;
        --it;
        int a=*it;
        ++it;
        int b=*it;
        ++it;
        int c=*it;
        ++it;
        int d=*it;
        ans+=(ll)i*(b-a)*(c-pos[i])+(ll)i*(d-c)*(pos[i]-b);
        se.insert(pos[i]);
    }
    cout<<ans<<endl;
}
