// Slower C++ solution:
#include<bits/stdc++.h>

#define ci const int&

#define Updl(x) (t[x].vl=Mrgl(t[x<<1].vl,t[x<<1|1].vl))

#define Updr(x) (t[x].vr=Mrgr(t[x<<1].vr,t[x<<1|1].vr))

#define pi pair<int,int>

#define f first

#define s second

using namespace std;

struct node{

	int l,r;

	pi vl,vr;

}t[400010];

int n,p[100010],pos[100010],l1,l2,r1,r2;

long long ans;

pi tmp;

pi Mrgl(const pi&x,const pi&y){

	return x.f>y.f?(pi){x.f,max(x.s,y.f)}:(pi){y.f,max(x.f,y.s)};

}

pi Mrgr(const pi&x,const pi&y){

	return x.f<y.f?(pi){x.f,min(x.s,y.f)}:(pi){y.f,min(x.f,y.s)};

}

void Build(ci x,ci l,ci r){

	t[x].l=l,t[x].r=r;

	if(l==r)return(void)(t[x].vr.f=pos[l],t[x].vr.s=n+1);

	int mid=l+r>>1;

	Build(x<<1,l,mid),Build(x<<1|1,mid+1,r),Updr(x);

}

void Changel(ci x,ci id,ci v){

	if(t[x].l==t[x].r)return(void)(t[x].vl.f=v);

	int mid=t[x].l+t[x].r>>1;

	id<=mid?Changel(x<<1,id,v):Changel(x<<1|1,id,v),Updl(x);

}

void Changer(ci x,ci id){

	if(t[x].l==t[x].r)return(void)(t[x].vr.f=n+1);

	int mid=t[x].l+t[x].r>>1;

	id<=mid?Changer(x<<1,id):Changer(x<<1|1,id),Updr(x);

}

pi Queryl(ci x,ci l,ci r){

	if(l>r)return(pi){0,0};

	if(t[x].l==l&&t[x].r==r)return t[x].vl;

	int mid=t[x].l+t[x].r>>1;

	return r<=mid?Queryl(x<<1,l,r):(l>mid?Queryl(x<<1|1,l,r):(Mrgl(Queryl(x<<1,l,mid),Queryl(x<<1|1,mid+1,r))));

}

pi Queryr(ci x,ci l,ci r){

	if(l>r)return(pi){n+1,n+1};

	if(t[x].l==l&&t[x].r==r)return t[x].vr;

	int mid=t[x].l+t[x].r>>1;

	return r<=mid?Queryr(x<<1,l,r):(l>mid?Queryr(x<<1|1,l,r):(Mrgr(Queryr(x<<1,l,mid),Queryr(x<<1|1,mid+1,r))));

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;++i)scanf("%d",&p[i]),pos[p[i]]=i;

	Build(1,1,n);

	for(int i=1;i<=n;++i){

		Changer(1,p[i]),Changel(1,p[i],i),tmp=Queryl(1,p[i]+1,n),l1=tmp.f,l2=tmp.s,tmp=Queryr(1,p[i]+1,n),r1=tmp.f,r2=tmp.s;

		ans+=1ll*(i-l1)*(r2-r1)*p[i]+1ll*(l1-l2)*(r1-i)*p[i];

	}

	printf("%lld",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 11.097642127197428x):
#include <iostream>

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

#include <limits>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <unordered_map>

#include <unordered_set>

#define lowbit(x) ( x&(-x) )

#define pi 3.141592653589793

#define e 2.718281828459045

#define INF 0x3f3f3f3f

#define eps 1e-6

#define HalF (l + r)>>1

#define lsn rt<<1

#define rsn rt<<1|1

#define Lson lsn, l, mid

#define Rson rsn, mid+1, r

#define QL Lson, ql, qr

#define QR Rson, ql, qr

#define myself rt, l, r

using namespace std;

typedef unsigned long long ull;

typedef unsigned int uit;

typedef long long ll;

const int maxN = 1e5 + 7;

int N, a[maxN], pre[maxN][2][2] = {0};

int t[2][maxN<<2];

inline void pushup(int *tree, int rt) { tree[rt] = max(tree[lsn], tree[rsn]); }

void update(int *tree, int rt, int l, int r, int qx, int val)

{

    if(l == r) { tree[rt] = val; return; }

    int mid = HalF;

    if(qx <= mid) update(tree, Lson, qx, val);

    else update(tree, Rson, qx, val);

    pushup(tree, rt);

}

inline int query(int *tree, int rt, int l, int r, int ql, int qr)

{

    if(ql <= l && qr >= r) return tree[rt];

    int mid = HalF;

    if(qr <= mid) return query(tree, QL);

    else if(ql > mid) return query(tree, QR);

    else return max(query(tree, QL), query(tree, QR));

}

ll ans = 0;

inline void solve(int id)

{

    int l = 1, r = id - 1, mid = 0, ith = 0;

    while(l <= r)

    {

        mid = (l + r)>>1;

        if(query(t[0], 1, 1, N, mid, id - 1) > a[id])

        {

            l = mid + 1;

            ith = mid;

        }

        else r = mid - 1;

    }

    if(ith == 0) return;

    pre[id][0][0] = ith;

    l = 1; r = ith - 1; ith = 0;

    int nex_id = r;

    while(l <= r)

    {

        mid = (l + r)>>1;

        if(query(t[0], 1, 1, N, mid, nex_id) > a[id])

        {

            l = mid + 1;

            ith = mid;

        }

        else r = mid - 1;

    }

    if(ith == 0)

    {

//        ans += 1LL * pre[id][0][0] * a[id];

        return;

    }

    pre[id][0][1] = ith;

//    ans += 1LL * (pre[id][0][0] - pre[id][0][1]) * a[id];

}

inline void finsh(int id)

{

    int l = id + 1, r = N, mid = 0, ith = 0;

    while(l <= r)

    {

        mid = (l + r)>>1;

        if(query(t[1], 1, 1, N, id + 1, mid) > a[id])

        {

            r = mid - 1;

            ith = mid;

        }

        else l = mid + 1;

    }

    if(ith == 0)

    {

        if(pre[id][0][0])

        {

//            ans += 1LL * (pre[id][0][0] - pre[id][0][1]) * (N - id) * a[id];

        }

        return;

    }

    pre[id][1][0] = ith;

    l = ith + 1; r = N; ith = 0;

    int nex_id = l;

    while(l <= r)

    {

        mid = (l + r)>>1;

        if(query(t[1], 1, 1, N, nex_id, mid) > a[id])

        {

            r = mid - 1;

            ith = mid;

        }

        else l = mid + 1;

    }

    if(ith == 0)

    {

//        ans += 1LL * (N - id) * (id - pre[id][0][0]) * a[id];

        return;

    }

    pre[id][1][1] = ith;

//    if(pre[id][0][0]) ans += 1LL * (pre[id][1][1] - pre[id][1][0]) * (pre[id][0][0] - pre[id][0][1]) * a[id];

//    else ans += 1LL * (pre[id][1][1] - pre[id][1][0]) * id * a[id];

}

int main()

{

    scanf("%d", &N);

    for(int i=1; i<=N; i++) scanf("%d", &a[i]);

    for(int i=1; i<=N; i++) pre[i][1][1] = pre[i][1][0] = N + 1;

    update(t[0], 1, 1, N, 1, a[1]);

    for(int i=2; i<=N; i++)

    {

        solve(i);

        update(t[0], 1, 1, N, i, a[i]);

    }

    update(t[1], 1, 1, N, N, a[N]);

    for(int i=N-1; i>=1; i--)

    {

        finsh(i);

        update(t[1], 1, 1, N, i, a[i]);

    }

    for(int i=1; i<=N; i++)

    {

        ans += 1LL * (pre[i][0][0] - pre[i][0][1]) * (pre[i][1][0] - i) * a[i];

        ans += 1LL * (i - pre[i][0][0]) * (pre[i][1][1] - pre[i][1][0]) * a[i];

    }

    printf("%lld\n", ans);

    return 0;

}