#include<bits/stdc++.h>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

template<typename T>
struct SegTree1{
    int num,bt;
    vector<T> node;

    void init(int num,T n){
        int i = 0,j=1;
        this->num = num;
        for (i = 0; j < num+1;i++)
            j*=2;
        j *= 2;
        bt = j / 2 - 1;

        node.resize((j - 1),n);
        for (int i = 0; i < num; i++){
            node[bt + i] = n;
        }
        for (int i = bt - 1; i >= 0;i--){
            node[i]=calc(node[i * 2 + 1], node[i * 2 + 2]);
        }
    }
    inline T calc(T& a,T& b){
        return min(a, b);
    }
    void sett(int x,T n){
        int i = bt+x;
        node[i] = n;
        while(i!=0){
            i = (i - 1) / 2;
            node[i] = calc(node[i * 2 + 1],node[i * 2 + 2]);
        }
    }
    inline T gett(int x){
        return node[bt + x];
    }
    T gett(int x,int y){
        int i = bt+x;
        T sss = 1e9;
        if(x==0&&y==num-1){
            return node[0];
        }
        if(x!=0){
            int i = bt + x-1;
            int j = 1,l=x-1,r=x-1;
            while(i!=0){
                if(i%2&&x<=l+j&&r+j<=y){
                    sss = calc(node[i + 1],sss);
                }
                i = (i - 1) / 2;
                j *= 2;
                l = l / j*j;
                r = r / j*j+j-1;
            }
        }

        i = bt + y+1;
        int j = 1,l=y+1,r=y+1;
        while(i!=0){
            if(i%2==0&&x<=l-j&&r-j<=y){
                sss = calc(node[i - 1],sss);
            }
            i = (i - 1) / 2;
            j *= 2;
            l = l / j*j;
            r = r / j*j+j-1;
        }
        return sss;
    }
};
template<typename T>
struct SegTree2{
    int num,bt;
    vector<T> node;

    void init(int num,T n){
        int i = 0,j=1;
        this->num = num;
        for (i = 0; j < num+1;i++)
            j*=2;
        j *= 2;
        bt = j / 2 - 1;

        node.resize((j - 1),n);
        for (int i = 0; i < num; i++){
            node[bt + i] = n;
        }
        for (int i = bt - 1; i >= 0;i--){
            node[i]=calc(node[i * 2 + 1], node[i * 2 + 2]);
        }
    }
    inline T calc(T& a,T& b){
        return max(a, b);
    }
    void sett(int x,T n){
        int i = bt+x;
        node[i] = n;
        while(i!=0){
            i = (i - 1) / 2;
            node[i] = calc(node[i * 2 + 1],node[i * 2 + 2]);
        }
    }
    inline T gett(int x){
        return node[bt + x];
    }
    T gett(int x,int y){
        int i = bt+x;
        T sss = 0;
        if(x==0&&y==num-1){
            return node[0];
        }
        
        if(x!=0){
            int i = bt + x-1;
            int j = 1,l=x-1,r=x-1;
            while(i!=0){
                if(i%2&&x<=l+j&&r+j<=y){
                    sss = calc(node[i + 1],sss);
                }
                i = (i - 1) / 2;
                j *= 2;
                l = l / j*j;
                r = r / j*j+j-1;
            }
        }

        i = bt + y+1;
        int j = 1,l=y+1,r=y+1;
        while(i!=0){
            if(i%2==0&&x<=l-j&&r-j<=y){
                sss = calc(node[i - 1],sss);
            }
            i = (i - 1) / 2;
            j *= 2;
            l = l / j*j;
            r = r / j*j+j-1;
        }
        return sss;
    }
};

SegTree1<ll> mn;
SegTree2<ll> mx;

ll N, P[101010];
ll A[101010];

ll i, j, k,ans;

int main(){
    scanf("%lld",&N);
    fornum(i,0,N){
        scanf("%lld", &P[i]);
        A[P[i]] = i + 1;
    }
    mn.init(N + 1, N + 1);
    mx.init(N + 1, 0);
    for (i = N; i > 0;i--)
    {
        ll ai = A[i];
        ll aa2, bb2;
        ll aa = mn.gett(ai, N);
        if(aa>=N){
            aa2 = N + 1 - aa;
        }else{
            aa2 = mn.gett(aa + 1, N) - aa;
        }
        aa = aa - ai;
        ll bb = mx.gett(1, ai);
        if(bb<=1){
            bb2 = bb;
        }else{
            bb2 = bb - mx.gett(1, bb - 1);
        }
        bb = ai - bb;
        //printf("%lld,%lld,%lld,%lld ", bb2, bb, aa, aa2);
        ans += (aa * bb2 + aa2 * bb) * i;
        mn.sett(ai, ai);
        mx.sett(ai, ai);
        //printf("%lld:%lld\n",i, ans);
    }
    printf("%lld", ans);

    return 0;
}

Measured memory_bytes: 5888