#include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define ll long long int
    #define ld long double
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define pb push_back
    #define f first
    #define s second
    
    using namespace std;

    ll tree[5000000],ar[100001];
    int n;

    void build(int node,int l,int r)
    {
        if(l==r)
        {
            tree[node]=ar[l];   //Change for min/sum
            return;
        }
        build(node*2,l,(l+r)/2);
        build(node*2+1,(l+r)/2+1,r);
        tree[node]=max(tree[node*2],tree[node*2+1]);    //Change for min/sum
    }
    
    ll query(int node,int l,int r,int i,int j,int x)
    {
        //cout<<l<<"...."<<r<<" "<<i<<" "<<j<<" "<<x<<" "<<tree[node]<<endl;
        if(j<l || r<i)
            return n+1;   //Change for min/sum
        if(tree[node]<x)
            return n+1;
        if(l==r)
            return l;
        //cout<<l<<"...."<<r<<" "<<i<<" "<<j<<" "<<x<<" "<<tree[node]<<endl;
        int z=query(node*2,l,(l+r)/2,i,j,x);
        if(z!=n+1)
            return z;
        return query(node*2+1,(l+r)/2+1,r,i,j,x); 
    }

    ll query2(int node,int l,int r,int i,int j,int x)
    {
        if(j<l || r<i)
            return 0;   //Change for min/sum
        if(tree[node]<x)
            return 0;
        if(l==r)
            return l;
        int z=query2(node*2+1,(l+r)/2+1,r,i,j,x);
        if(z!=0)
            return z;
        return query2(node*2,l,(l+r)/2,i,j,x);
    }


    int main()
    {
        std::ios::sync_with_stdio(false);
        int T;
        T=1;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            int i,j;
            cin>>n;
            for(i=1;i<=n;++i)
                cin>>ar[i];
            build(1,1,n);
            ll nx,nx2,pre,pre2,a,b;
            ll ans=0;
            for(i=1;i<=n;++i)
            {
                nx=query(1,1,n,i+1,n,ar[i]);
                nx2=query(1,1,n,nx+1,n,ar[i]);
                pre=query2(1,1,n,1,i-1,ar[i]);
                pre2=query2(1,1,n,1,pre-1,ar[i]);
                //cout<<i<<" "<<ar[i]<<" "<<nx<<" "<<nx2<<" "<<pre<<" "<<pre2<<endl;
                if(pre==0 && nx==n+1)
                    continue;
                if(nx!=n+1)
                {
                    a=nx2-nx;
                    b=i-pre;
                    //cout<<a<<"..."<<b<<endl;
                    ans=ans+a*b*ar[i];
                }
                if(pre!=0)
                {
                    a=nx-i;
                    b=pre-pre2;
                    //cout<<a<<"###"<<b<<endl;
                    ans=ans+a*b*ar[i];
                }
                //cout<<ans<<endl;
            }
            cout<<ans<<endl;
        }
        return 0;
    }


Measured memory_bytes: 4352