/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

template<class T,class E> struct LSeg{
    typedef function<T(T,T)> F;
    typedef function<T(T,E)> G;
    typedef function<E(E,E)> H;
    typedef function<E(E,int)> P;
    int n;F f;G g;H h;T et;E ee;P p;
    vector<T> dat;
    vector<E> lazy;
    LSeg(int n_,F f_,G g_,H h_,T et_,E ee_,P p_=[](E a,int b){return a;}){
        f=f_;g=g_;h=h_;et=et_;ee=ee_;p=p_;
        n=1;
        while(n<n_) n*=2;
        dat.resize(2*n-1,et);
        lazy.resize(2*n-1,ee);
    }
    inline void prop(int k,int l,int r){
        if(lazy[k]==ee) return;
        if(r-l>1){
            lazy[k*2+1]=h(lazy[k*2+1],lazy[k]);
            lazy[k*2+2]=h(lazy[k*2+2],lazy[k]);
        }
        dat[k]=g(dat[k],p(lazy[k],r-l));
        lazy[k]=ee;
    }
    T ud(int be,int en,E t,int k,int l,int r){
        prop(k,l,r);
        if(r<=be||en<=l) return dat[k];
        if(be<=l&&r<=en){
            lazy[k]=h(lazy[k],t);
            return g(dat[k],p(lazy[k],r-l));
        }
        return dat[k]=f(ud(be,en,t,k*2+1,l,(l+r)/2),ud(be,en,t,k*2+2,(l+r)/2,r));
    }
    T ud(int be,int en,E t){
        ud(be,en,t,0,0,n);
    }
    T gt(int be,int en,int k,int l,int r){
        prop(k,l,r);
        if(r<=be||en<=l) return et;
        if(be<=l&&r<=en) return dat[k];
        T vl=gt(be,en,k*2+1,l,(l+r)/2),vr=gt(be,en,k*2+2,(l+r)/2,r);
        return f(vl,vr);
    }
    T gt(int be,int en){
        return gt(be,en,0,0,n);
    }
};

template<class T> void cc(vector<T> a,map<T,int>& nm,vector<int>& c){
    sort(a.begin(),a.end());
    fr(i,a.size()){
        if(i<a.size()-1&&a[i]==a[i+1]) continue;
        nm[a[i]]=c.size();
        c.push_back(a[i]);
    }
}

class ESecondSum {
public:
    void solve(istream& in, ostream& out) {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        int n;
        in>>n;
        vector<int> p(n);
        for(auto&i:p) in>>i;
        vector<int> r1(n),r2(n),l1(n),l2(n);
        using P=pair<int,int>;
        auto mx=[](P a,P b){
            vector<int> c(4);
            c[0]=a.first,c[1]=b.first,c[2]=a.second,c[3]=b.second;
            sort(c.begin(),c.end());
            return P(c[3],c[2]);
        };
        LSeg<P,P> sg1(n,mx,mx,mx,P(-1,-1),P(-1,-1));
        fr(i,n){
            tie(l1[i],l2[i])=sg1.gt(p[i],p[i]+1);
            sg1.ud(0,p[i],P(i,-1));
        }
        auto mn=[](P a,P b){
            vector<int> c(4);
            c[0]=a.first,c[1]=b.first,c[2]=a.second,c[3]=b.second;
            sort(c.begin(),c.end());
            return P(c[0],c[1]);
        };
        LSeg<P,P> sg2(n,mn,mn,mn,P(n,n),P(n,n));
        ifr(i,n){
            tie(r1[i],r2[i])=sg2.gt(p[i],p[i]+1);
            sg2.ud(0,p[i],P(i,n));
        }
        ll ans=0;
        //fr(i,n) cout<<l2[i]<<" "<<l1[i]<<" "<<r1[i]<<" "<<r2[i]<<endl;
        fr(i,n){
            ans+=p[i]*((ll)(l1[i]-l2[i])*(r1[i]-i)+(ll)(i-l1[i])*(r2[i]-r1[i]));
        }
        out<<ans<<endl;
    }
};

int main() {
    ESecondSum solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 10496