// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#include <map>

#include <set>

#include <ctime>

#include <queue>

#include <stack>

#include <cmath>

#include <vector>

#include <bitset>

#include <cstdio>

#include <cctype>

#include <string>

#include <numeric>

#include <cstring>

#include <cassert>

#include <climits>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std ;

#define rep(i, a, b) for (register ll i = (a); i <= (b); ++i)

#define per(i, a, b) for (register ll i = (a); i >= (b); --i)

#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)

#define cont(i, x) for (int i = head[x]; i; i = edge[i].nex)

#define clr(a) memset(a, 0, sizeof(a))

#define ass(a, cnt) memset(a, cnt, sizeof(a))

#define cop(a, b) memcpy(a, b, sizeof(a))

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

#define all(x) x.begin(), x.end()

#define SC(t, x) static_cast <t> (x)

#define ub upper_bound

#define lb lower_bound

#define pqueue priority_queue

#define mp make_pair

#define pb push_back

#define pof pop_front

#define pob pop_back

#define fi first

#define se second

#define y1 y1_

#define Pi acos(-1.0)

#define iv inline void

#define enter cout << endl

#define siz(x) ((int)x.size())

#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)

typedef double db ;

typedef long long ll ;

typedef unsigned long long ull ;

typedef pair <int, int> pii ;

typedef vector <int> vi ;

typedef vector <pii> vii ;

typedef queue <int> qi ;

typedef queue <pii> qii ;

typedef set <int> si ;

typedef map <int, int> mii ;

typedef map <string, int> msi ;

const int maxn = 5e5 + 10 ;

const int inf = 0x3f3f3f3f ;

const int iinf = 1 << 30 ;

const ll linf = 2e18 ;

const ll mod = 1e9 + 7 ;

const double eps = 1e-7 ;

template <class T> void read(T &a)

{

	int f = 1 ; a = 0;

	char ch = getchar() ;

	while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }

	while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }

	a *= f;

}



ll n, ans;



ll p[maxn];



ll st[maxn][20], lg[maxn];



void init()

{

	rep(i, 1, n) st[i][0] = p[i];

	ll tot = 0;

	rep(i, 1, n)

	{

		if((1 << (tot + 1)) < i) tot ++;

		lg[i] = tot;

	}

	if(tot >= 20)

	{

		puts("0");

		exit(0);

	}

	rep(i, 1, tot) rep(j, 1, n)

	{

		if(!(j + (1 << (i - 1)) < maxn))

		{

			puts("0");

			exit(0);

		}

		if(!(j + (1 << (i - 1)) > 0))

		{

			puts("0");

			exit(0);

		}

		st[j][i] = max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);

	}

	return ;

}



#define query(l, r) max(st[l][lg[r - l + 1]], st[r - (1 << lg[r - l + 1]) + 1][lg[r - l + 1]])



ll bsearch(ll l, ll r, ll x, ll typ)

{

	ll s = l, e = r;

	ll ret = typ * (n + 1);

	while(l <= r)

	{

		ll mid = (l + r) >> 1;

		if(typ == 1)

		{

			if(query(s, mid) > x) r = mid - 1, ret = mid;

			else l = mid + 1;

		}

		else

		{

			if(query(mid, e) > x) l = mid + 1, ret = mid;

			else r = mid - 1;

		}

	}

	return ret;

}



signed main()

{

	scanf("%lld", &n);

	rep(i, 1, n) scanf("%lld", &p[i]);

	init();

	rep(i, 1, n)

	{

		ll tl = bsearch(1, i - 1, p[i], 0), tr = bsearch(i + 1, n, p[i], 1);

		ll sl = bsearch(1, tl - 1, p[i], 0), sr = bsearch(tr + 1, n, p[i], 1);

		ans += p[i] * (sr - tr) * (i - tl);

		ans += p[i] * (tl - sl) * (tr - i);

	}

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

	return 0;

}


// Fastest known solution for this problem: