//#include "stdc++.h"
#include<bits/stdc++.h>
#include<iostream>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
typedef vector<int> vi;
#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))
#define sz(x) (int)(x.size())
#define ff first
#define ss second
#define endl "\n"
#define int long long int
inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p*p)%m;if(n%2) return (p*a)%m;else return p;}
const ll MOD = 1000000007;
const ll MOD1=1000000009;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
/*
 shuffle(x,x+n,rng) // shuffling elements of x in random order
 */
int st[400001];int n;
void update(int i,int l,int r,int in,int v)
{
    if(l>r)
        return;
    if(in<l||in>r)
        return;
    if(l==r)
    {
        st[i]=v;
        return;
    }
    int m=(l+r)/2;
    update(2*i+1,l,m,in,v);
    update(2*i+2,m+1,r,in,v);
    st[i]=max(st[2*i+1],st[2*i+2]);
}
int query(int i,int l,int r,int qs,int qe)
{
    if(qs>qe)
        return -1;
    if(qs>r||qe<l)
        return -1;
    if(qs<=l&&qe>=r)
        return st[i];
    int m=(l+r)/2;
    return max(query(2*i+1,l,m,qs,qe),query(2*i+2,m+1,r,qs,qe));
}

void update1(int i,int l,int r,int in,int v)
{
    if(l>r)
        return;
    if(in<l||in>r)
        return;
    if(l==r)
    {
        st[i]=v;
        return;
    }
    int m=(l+r)/2;
    update1(2*i+1,l,m,in,v);
    update1(2*i+2,m+1,r,in,v);
    st[i]=min(st[2*i+1],st[2*i+2]);
}
int query1(int i,int l,int r,int qs,int qe)
{
    if(qs>qe)
        return n;
    if(qs>r||qe<l)
        return n;
    if(qs<=l&&qe>=r)
        return st[i];
    int m=(l+r)/2;
    return min(query1(2*i+1,l,m,qs,qe),query1(2*i+2,m+1,r,qs,qe));
}
int32_t main()
{
    IOS;
   // int n;
    cin>>n;
    int p[n];
    for(int i=0;i<n;i++)
    {
        cin>>p[i];
        p[i]--;
    }
    int in,mx1[n],mx2[n],mx3[n],mx4[n],ans=0;
    for(int i=0;i<=4*n;i++)
        st[i]=-1;
    for(int i=0;i<n;i++)
    {
        in=query(0,0,n-1,p[i]+1,n-1);
        mx1[i]=in;
        if(in!=-1)
        {
            update(0,0,n-1,p[in],-1);
            mx2[i]=query(0,0,n-1,p[i]+1,n-1);
            update(0,0,n-1,p[in],in);
        }
        else
            mx2[i]=-1;
        update(0,0,n-1,p[i],i);
    }
    for(int i=0;i<=4*n;i++)
        st[i]=n;
    for(int i=n-1;i>=0;i--)
    {
        in=query1(0,0,n-1,p[i]+1,n-1);
        mx3[i]=in;
        if(in!=n)
        {
            update1(0,0,n-1,p[in],n);
            mx4[i]=query1(0,0,n-1,p[i]+1,n-1);
            update1(0,0,n-1,p[in],in);
        }
        else
            mx4[i]=n;
        update1(0,0,n-1,p[i],i);
    }
    /*
    for(int i=0;i<n;i++)
    {
        cout<<mx2[i]<<" "<<mx1[i]<<" "<<mx3[i]<<" "<<mx4[i]<<endl;
    }
     */
    for(int i=0;i<n;i++)
    {
            ans+=(p[i]+1)*((mx4[i]-mx3[i])*(i-mx1[i]));
            ans+=(p[i]+1)*((mx1[i]-mx2[i])*(mx3[i]-i));
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 7296