#include<bits/stdc++.h>
using namespace std;
int a[100001],ST[(1<<18)];
long long ans=0;
void build(int l,int r,int p){
    if(l==r){
        ST[p]=r;
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    ST[p] = (a[ST[p*2]] > a[ST[p*2+1]]) ? ST[p*2] : ST[p*2+1];
}
int query(int l,int r ,int p,int i,int j){
    if(l>j | r<i){
        return -1;
    }
    if(l>=i && r<=j){
        return ST[p];
    }
    int mid=(l+r)/2;
    int p1=query(l,mid,p*2,i,j);
    int p2=query(mid+1,r,p*2+1,i,j);
    if(p1 == -1)
        return p2;
    if(p2 == -1)
        return p1;
    return (a[p1] > a[p2]) ? p1 : p2;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,n,1);
    for(int i=1;i<=n;i++){
        int l=1,r=i-1,pre1=0,pre2,next1,next2;

        while(l<=r){
            if(l==r){
                int pos=query(1,n,1,l,l);
                if(a[pos]>a[i]){
                    pre1=pos;
                }
                break;
            }
            int mid=(l+r)/2;
            int pos=query(1,n,1,mid+1,r);
            if(a[pos]>a[i]){
                pre1=pos;
                l=pos+1;
            }
            else{
                pos=query(1,n,1,l,mid);
                if(a[pos]>a[i]){
                    pre1=pos;
                    l=pos+1;
                }
                else{
                    break;
                }

            }
        }
        l=1,r=pre1-1,pre2=0;
        while(l<=r){
            if(l==r){
                int pos=query(1,n,1,l,l);
                if(a[pos]>a[i]){
                    pre2=pos;
                }
                break;
            }
            int mid=(l+r)/2;
            int pos=query(1,n,1,mid+1,r);
            if(a[pos]>a[i]){
                pre2=pos;
                l=pos+1;
            }
            else{
                pos=query(1,n,1,l,mid);
                if(a[pos]>a[i]){
                    pre2=pos;
                    l=pos+1;
                }
                else{
                    break;
                }

            }
        }
        l=i+1,r=n,next1=n+1;
        while(l<=r){
            if(l==r){
                int pos=query(1,n,1,l,l);
                if(a[pos]>a[i]){
                    next1=pos;
                }
                break;
            }
            int mid=(l+r)/2;
            int pos=query(1,n,1,l,mid);
            if(a[pos]>a[i]){
                next1=pos;
                r=pos-1;
            }
            else{
                pos=query(1,n,1,mid+1,r);
                if(a[pos]>a[i]){
                    next1=pos;
                    r=pos-1;
                }
                else{
                    break;
                }

            }
        }
        l=next1+1,r=n,next2=n+1;
        while(l<=r){
            if(l==r){
                int pos=query(1,n,1,l,l);
                if(a[pos]>a[i]){
                    next2=pos;
                }
                break;
            }
            int mid=(l+r)/2;
            int pos=query(1,n,1,l,mid);
            if(a[pos]>a[i]){
                next2=pos;
                r=pos-1;
            }
            else{
                pos=query(1,n,1,mid+1,r);
                if(a[pos]>a[i]){
                    next2=pos;
                    r=pos-1;
                }
                else{
                    break;
                }

            }
        }
        long long cnt=0;
        cnt+=(long long)((pre1-pre2)*(next1-i));
        cnt+=(long long)((next2-next1)*(i-pre1));
        ans+=(long long)(cnt*a[i]);
       // cout<<pre1<<" "<<pre2<<" "<<next1<<" "<<next2<<endl;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1664