#include<iostream>
#include<algorithm>
#include<map>
#include<set>
using lint=int64_t;
using namespace std;

int main()
{
	lint N;
	cin >> N;

	map<int,lint> indexof;
	for(lint i=1;i<=N;i++)
	{
		lint val;
		cin >> val;
		indexof[val]=i;
	}

	multiset<lint> ipool;
	ipool.insert(0);
	ipool.insert(0);
	ipool.insert(N+1);
	ipool.insert(N+1);
	
	lint ans=0;
	for(lint i=N;i>=1;i--)
	{
		lint l2,l1,r1,r2;
		auto itr=ipool.lower_bound(indexof[i]);
		r1=*itr;
		++itr;
		r2=*itr;
		--itr;--itr;
		l1=*itr;
		--itr;
		l2=*itr;

		ans+=(indexof[i]-l1)*(r2-r1)*i;
		ans+=(l1-l2)*(r1-indexof[i])*i;

		ipool.insert(indexof[i]);
	}

	cout << ans << endl;
	return 0;
}

