#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const ll BIG=1e15;

int main(){
    int N;cin>>N;
    vector<int> d(N+1);
    for(int i=1;i<=N;i++){
        int x; cin>>x;
        d.at(x)=i;
    }

    ll ans=0;
    multiset<int> S;
    S.insert(N+1);
    S.insert(N+1);
    S.insert(0);
    S.insert(0);
    for(ll i=N;i>=1;i--){
        S.insert(d.at(i));
        auto itr=S.find(d.at(i));
        ll  m0,l1,l2,r1,r2;
        itr++; r1=*itr;
        itr++; r2=*itr;
        itr--; itr--; m0=*itr;
        itr--; l2=*itr;
        itr--; l1=*itr;
        ans+=i*((r2-r1)*(m0-l2)+(r1-m0)*(l2-l1));
    }
    cout<<ans<<endl;


}