#include<bits/stdc++.h> 
using namespace std; 
typedef  pair<int, int> iPair; 
//#define mod 1000000007
#define pb push_back
typedef long long ll;
typedef long double ld;
#define FOR(i,n) for(i=0;i<n;i++)
#define FORE(i,n) for(i=0;i<=n;i++)
 
 
ll gcd(ll a , ll b)
{
   if(b==0) return a;
   a%=b;
   return gcd(b,a);
   
}
    
ll maxl(ll a,ll b){
    if(a>b)return a;
    return b;
}
 
ll minl(ll a,ll b){
    if(a>b)return b;
    return a;
}
 
ll mod = 998244353;
 
ll mulmod(ll a, ll b,ll c){ 
    ll res = 0; 
    a = a % c; 
    while (b > 0){ 
        if (b % 2 == 1){ 
            res = (res + a) % c;
        }
        a = (a * 2) % c; 
        b /= 2; 
    } 
    return res % c; 
}
 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
        if (arr[mid] == x) 
            return mid; 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
        return binarySearch(arr, mid + 1, r, x); 
    } 
    return -1; 
} 
 
int a[100005];
int tree[200005];
 
void build(int st,int low,int high){
    if(low==high){
        tree[st] = a[high]%2;
        return;
    }
    int mid = low+(high-low)/2;
    build(2*st,low,mid);
    build(2*st+1,mid+1,high);
    tree[st] = tree[2*st]+tree[2*st+1];
}
 
void update(int st,int start,int end,int ind,int val){
    if(start==end){
        tree[st] = val%2;
        return;
    }
    int mid = start+(end-start)/2;
    if(ind<=mid){
        update(2*st,start,mid,ind,val);
    }
    else update(2*st+1,mid+1,end,ind,val);
    tree[st] = tree[2*st]+tree[2*st+1];
}
 
int query(int st,int start,int end,int low,int high){
    if(start>high || end<low)return 0;
    int mid = start + (end-start)/2;
    if(start==low && end==high){
        return tree[st];
    }
    if(low>mid)return query(2*st+1,mid+1,end,low,high);
    if(high<=mid)return query(2*st,start,mid,low,high);
    return query(2*st,start,mid,low,mid)+query(2*st+1,mid+1,end,mid+1,high);
}

int main()
{
        ios_base::sync_with_stdio(false);
        int n;
        cin >> n;
        ll p[n];
        vector<ll> m(n+1);
        ll ans = 0;
        for(int i=0;i<n;i++){
            cin >> p[i];
            m[p[i]] = i;
        }
        multiset<ll> s;
        for(ll i=n;i>=1;i--){
            int a,b,x,y;
            if(i==n){
                s.insert(m[i]);
                continue;
            }
            auto it = s.upper_bound(m[i]);
            if(it!=s.end()){
                x = *it;
            }
            else {
                x = n;
            }
            it = s.upper_bound(x);
            if(it!=s.end()){
                y = *it;
            }
            else y = n; 
            it = s.lower_bound(m[i]);
            if(it!=s.begin()){
                it--;
                a = *it;
            }
            else{
                a = -1;
            }
            it = s.lower_bound(a);
            if(it!=s.begin()){
                it--;
                b = *it;
            }
            else b = -1;
            ll count = (a-b)*(x-m[i]) + (y-x)*(m[i]-a);
            ans+=i*count;
            s.insert(m[i]);
        }
        cout << ans << endl;
        return 0;
}

Measured memory_bytes: 6528