#include <bits/stdc++.h>
#define ll long long
#define read(x) scanf("%d",&x)
using namespace std;
const int maxn = 1e5 + 10;

int n;
int p[maxn], pos[maxn];
multiset <int> s;
multiset<int>::iterator a1,a2,x,y,b1,b2;

int main()
{   
	cin>>n;
	for(int i=1;i<=n;i++) {
		read(p[i]);
		pos[p[i]] = i;
	}
	s.insert(0); s.insert(0);
	s.insert(n+1); s.insert(n+1);
	ll res = 0;
	for (int i=n;i>=1;i--){
		x = y = s.upper_bound(pos[i]);  //第一个大于等于pos[i]
		a2 = --x; a1 = --x;
		b1 = y ; b2 = ++y;
		res += 1ll*(*a2-*a1)*(*b1-pos[i])*i;
		res += 1ll*(pos[i]-*a2)*(*b2-*b1)*i;
		s.insert(pos[i]);
	}
	cout<<res<<endl;
	return 0;
}