//
/*==========================================================*/
/*    Template ver 2017-0720    |    Created by JollyBee    */
/* DOMINUS pascit me, et nihil mihi deerit (Psalmorum 23:1) */
/*==========================================================*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
const double EPS=(double)1e-9;
const double PI=(double)acos(-1.0);
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define FOR(i,n) for(int i=0;i<n;i++)
#define REPP(i,l,r,c) for(int i=l;i<=r;i+=c)
#define REP(i,l,r) REPP(i,l,r,1)
#define FORD(i,n) for(int i=n-1;i>=0;i--)
#define REVV(i,l,r,c) for(int i=l;i>=r;i-=c)
#define REV(i,l,r) REVV(i,l,r,1)
//random
int irand(int lo, int hi){
    return (((double)rand())/(RAND_MAX+1.0)) * (hi-lo+1) + lo;
}
//ll to string
string toString(ll x) {
    stringstream ss;
    ss << x;
    return ss.str();
}
//string to ll
ll toNumber(string S) {
    ll ret;
    sscanf(S.c_str(),"%lld",&ret);
    return ret;
}
// std::fill(start, end, value);
// for(auto it: DS){}

const int INF=(int)2e9;
const ll MOD=(ll)1e9+7;
/*==========================================================*/
/*                     END OF TEMPLATE                      */
/* DOMINUS pascit me, et nihil mihi deerit (Psalmorum 23:1) */
/*==========================================================*/

const int N = (int)1e5;

class BIT{
    int dat[N+5];
    //
    int LSOne(int a){ return a&-a; }
public:
    int reset(){
        FOR(i,N+3) dat[i] = 0;
        return 0;
    }
    int upd(int pos, int val=1){
        REPP(i,pos,N,LSOne(i)) dat[i] += val;
        return 0;
    }
    int que(int pos){
        int res = 0;
        REVV(i,pos,1,LSOne(i)) res += dat[i];
        return res;
    }
    int que(int a, int b){
        return que(b) - que(a-1);
    }
};

pii dat[N+5];
BIT ds;

int main(){
    // reset
    ds.reset();
    // input
    int n; scanf("%d", &n);
    REP(i,1,n) scanf("%d", &dat[i].fi), dat[i].se = i;
    sort(dat+1, dat+1+n);
    //
    ll res = (ll)0;
    REP(i,1,n-1){
        int pos = dat[i].se;
        ds.upd(pos);
        // find left
        int reta = pos;
        for(int lo=1,hi=pos-1; lo<=hi; ){
            int mid = (lo+hi) / 2;
            int key = ds.que(mid,pos-1);
            //
            if(key+1 < pos-mid){
                lo = mid+1;
            } else {
                hi = mid-1;
                reta = mid;
            }
        }
        // find right
        int retb = pos;
        for(int lo=pos+1,hi=n; lo<=hi; ){
            int mid = (lo+hi) / 2;
            int key = ds.que(pos+1,mid);
            //
            if(key+1 >= mid-pos){
                lo = mid+1;
                retb = mid;
            } else {
                hi = mid-1;
            }
        }
        // find left 2
        int retae = pos;
        for(int lo=1,hi=pos-1; lo<=hi; ){
            int mid = (lo+hi) / 2;
            int key = ds.que(mid,pos-1);
            //
            if(key != pos-mid){
                lo = mid+1;
            } else {
                hi = mid-1;
                retae = mid;
            }
        }
        // find right 2
        int retbe = pos;
        for(int lo=pos+1,hi=n; lo<=hi; ){
            int mid = (lo+hi) / 2;
            int key = ds.que(pos+1,mid);
            //
            if(key == mid-pos){
                lo = mid+1;
                retbe = mid;
            } else {
                hi = mid-1;
            }
        }
        // count
        reta = pos - reta;  retae = pos - retae + 1;
        retb = retb - pos;  retbe = retbe - pos + 1;
        reta -= retae - 1;
        retb -= retbe - 1;
        res += (ll)dat[i].fi * (ll)(reta*retbe + retb*retae);
    }
    // print
    printf("%lld\n", res);
    return 0;
}


Measured memory_bytes: 1408