#include <bits/stdc++.h>
using namespace std;

template<typename T>
istream& operator >> (istream& istr, vector<T>& vec){
    for(T& x: vec) istr >> x;
    return istr;
}

template<typename T>
ostream& operator << (ostream& ostr, vector<T>& vec){
    if(!vec.empty()){
        ostr << vec.front();
        for(auto itr = ++vec.begin(); itr != vec.end(); itr++)
            ostr << " " << *itr;
    }
    return ostr;
}

template<typename T>
ostream& operator << (ostream& ostr, vector<vector<T>>& mat){
    if(!mat.empty()){
        ostr << mat.front();
        for(auto itr = ++mat.begin(); itr != mat.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

template<typename T, typename U>
ostream& operator << (ostream& ostr, pair<T,U>& p){
    ostr << p.first << " " << p.second;
    return ostr;
}

template<typename T, typename U>
ostream& operator << (ostream& ostr, vector<pair<T,U>>& mat){
    if(!mat.empty()){
        ostr << mat.front();
        for(auto itr = ++mat.begin(); itr != mat.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

typedef long long ll;
typedef vector<ll> vll;
// vll x(n); x[i]=a;
typedef vector<pair<ll,ll>> vpll;
// vpll x(n); x[i]={a,b}; x[i].first/second;
typedef vector<vector<ll>> vvll;
// vvll x(m,vi(n)); x[i][j]=a;

#define REP(i,n) for(ll i=0; i<(n); i++)
#define RREP(i,n) for(ll i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(ll i=(a); i<(b); i++)
#define FORR(i,a,b) for(ll i=(b)-1; i>=(a); i--)
#define dump(x) cout << #x << " = " << (x) << endl
#define all(x) (x).begin(),(x).end()
// sort(all(x));

void left(vll& p, vvll& q){

}

int main(){
    ll n, ans = 0, tmp = 0, idx = 0;
    cin >> n;

    vll p(n);
    cin >> p;

    vvll q(n,vll(4,0));
    REP(i,n){
        if(i == 0){
            q[i][0] = -1;
            q[i][1] = -1;
        }
        else if(p[i] > p[i-1] && q[i-1][0] == -1){
            q[i][0] = q[i-1][0];
            q[i][1] = q[i-1][1];
        }
        else if(p[i] > p[i-1] && p[i] < p[q[i-1][0]] && q[i-1][1] == -1){
            q[i][0] = q[i-1][0];
            q[i][1] = q[i-1][1];
        }
        else if(p[i] > p[i-1] && p[i] < p[q[i-1][0]] && p[i] < p[q[i-1][1]]){
            q[i][0] = q[i-1][0];
            q[i][1] = q[i-1][1];
        }
        else{
            RREP(j,i){
                if(p[j]>p[i]){
                    q[i][tmp] = j;
                    tmp++;
                    if(tmp == 2) break;
                }
            }
            if(tmp == 0){
                q[i][0] = -1;
                q[i][1] = -1;
            }
            else if(tmp == 1){
                q[i][1] = -1;
            }
        }
        tmp = 0;
    }

    tmp = 0;

    RREP(i,n){
        if(i == n-1){
            q[i][2] = n;
            q[i][3] = n;
        }
        else if(p[i] > p[i+1] && q[i+1][2] == n){
            q[i][2] = q[i+1][2];
            q[i][3] = q[i+1][3];
        }
        else if(p[i] > p[i+1] && p[i] < p[q[i+1][2]] && q[i+1][3] == n){
            q[i][2] = q[i+1][2];
            q[i][3] = q[i+1][3];
        }
        else if(p[i] > p[i+1] && p[i] < p[q[i+1][2]] && p[i] < p[q[i+1][3]]){
            q[i][2] = q[i+1][2];
            q[i][3] = q[i+1][3];
        }
        else{
            REP(j,n-i-1){
                if(p[j+i+1]>p[i]){
                    q[i][tmp+2] = j+i+1;
                    tmp++;
                    if(tmp == 2) break;
                }
            }
            if(tmp == 0){
                q[i][2] = n;
                q[i][3] = n;
            }
            else if(tmp == 1){
                q[i][3] = n;
            }
        }
        tmp = 0;
    }

    REP(i,n){
        ans += p[i]*(q[i][0]-q[i][1])*(q[i][2]-i);
        ans += p[i]*(q[i][3]-q[i][2])*(i-q[i][0]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8064