#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef   long long int ll;
typedef unsigned long long int sll;
typedef  double ld;
#define A 1000000007ll
#define B 998244353ll
#define C 1000000000000000001ll
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define oset tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define pb push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI 3.14159265358979323

const ll MAXN = 100005;
pair<ll,ll> t[4*MAXN];

void build(ll a[], ll v, ll tl, ll tr) 
{
    if (tl == tr) 
        t[v] = {a[tl],C};
    else 
    {
        ll tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        ll x[4]={t[v*2].first,t[v*2].second,t[v*2+1].first,t[v*2+1].second};
        sort(x,x+4);
        t[v] = {x[0],x[1]};
    }
}

pair<ll,ll> tmi(ll v, ll tl, ll tr, ll l, ll r) 
{
    if (l > r) 
        return {C,C};
    if (l == tl && r == tr) 
        return t[v];
    ll tm = (tl + tr) / 2;
    pair<ll,ll> p = tmi(v*2, tl, tm, l, min(r, tm)), q = tmi(v*2+1, tm+1, tr, max(l, tm+1), r);
    ll x[4]={p.first,p.second,q.first,q.second};
   	sort(x,x+4);
    return {x[0],x[1]};
}

void update(ll v, ll tl, ll tr, ll pos, ll new_val) 
{
    if (tl == tr) 
    	t[v] = {new_val,C};
    else 
    {
        ll tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        ll x[4]={t[v*2].first,t[v*2].second,t[v*2+1].first,t[v*2+1].second};
        sort(x,x+4);
        t[v] = {x[0],x[1]};
    }
}
void build1(ll a[], ll v, ll tl, ll tr) 
{
    if (tl == tr) 
        t[v] = {-C,a[tl]};
    else 
    {
        ll tm = (tl + tr) / 2;
        build1(a, v*2, tl, tm);
        build1(a, v*2+1, tm+1, tr);
        ll x[4]={t[v*2].first,t[v*2].second,t[v*2+1].first,t[v*2+1].second};
        sort(x,x+4);
        t[v] = {x[2],x[3]};
    }
}
pair<ll,ll> tma(ll v, ll tl, ll tr, ll l, ll r) 
{
    if (l > r) 
        return {-C,-C};
    if (l == tl && r == tr) 
        return t[v];
    ll tm = (tl + tr) / 2;
    pair<ll,ll> p = tma(v*2, tl, tm, l, min(r, tm)), q = tma(v*2+1, tm+1, tr, max(l, tm+1), r);
    ll x[4]={p.first,p.second,q.first,q.second};
   	sort(x,x+4);
    return {x[2],x[3]};
}
void update1(ll v, ll tl, ll tr, ll pos, ll new_val) 
{
    if (tl == tr) 
    	t[v] = {-C,new_val};
    else 
    {
        ll tm = (tl + tr) / 2;
        if (pos <= tm)
            update1(v*2, tl, tm, pos, new_val);
        else
            update1(v*2+1, tm+1, tr, pos, new_val);
        ll x[4]={t[v*2].first,t[v*2].second,t[v*2+1].first,t[v*2+1].second};
        sort(x,x+4);
        t[v] = {x[2],x[3]};
    }
}

int main() 
{
    FAST;
    ll n;
    cin>>n;
    ll a[n+1],p[n];
    for(int i=0;i<n;i++)
    	cin>>p[i];
    for(int i=0;i<=n;i++)
    	a[i]=-C;
    ll x1[n+1],x2[n+1],x3[n+1],x4[n+1];
    ll ans=0;
    build1(a, 1, 1, n);
    for(int i=0;i<n;i++)
    {
    	update1(1, 1, n, p[i], i);
    	pair<ll,ll> q = tma(1, 1, n, p[i]+1, n);
    	if(q.second==-C && q.first==-C)
    	{	
    		x1[i]=0;
    		x2[i]=i+1;
    	}
    	if(q.second!=-C && q.first==-C)
    	{
    		x1[i]=q.second+1;
    		x2[i]=i-q.second;
    	}
    	if(q.second!=-C && q.first!=-C)
    	{
    		x1[i]=q.second-q.first;
    		x2[i]=i-q.second;
    	}
    }
    for(int i=0;i<=n;i++)
    	a[i]=C;
    build(a, 1, 1, n);
    for(int i=n-1;i>=0;i--)
    {
    	update(1, 1, n, p[i], i);
    	pair<ll,ll> q = tmi(1, 1, n, p[i]+1, n);
    	if(q.second==C && q.first==C)
    	{	
    		x4[i]=0;
    		x3[i]=n-i;
    	}
    	if(q.second==C && q.first!=C)
    	{
    		x4[i]=n-q.first;
    		x3[i]=q.first-i;
    	}
    	if(q.second!=C && q.first!=C)
    	{
    		x4[i]=q.second-q.first;
    		x3[i]=q.first-i;
    	}
    }
    for(int i=0;i<n;i++)
    {
    	ans+=p[i]*((x1[i]*x3[i])+(x2[i]*x4[i]));
    	//cout<<x1[i]<<' '<<x2[i]<<' '<<x3[i]<<' '<<x4[i]<<'\n';
    }
    cout<<ans;
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Measured memory_bytes: 11136