#include<bits/stdc++.h>

using namespace std;

const int maxn=100005;

int n;
int p[maxn];
int x[maxn];
int c[maxn];
set<int> s;
 
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>x[i];
	for(int i=1;i<=n;i++){
		p[x[i]]=i;
	}		
	long long ans=0;
	s.insert(0);s.insert(n+1);
	for(int i=n;i>=1;i--){
		set<int>::iterator it2=s.lower_bound(p[i]),it1=it2;
		it1--;
		long long q1=0;
		if(it1!=s.begin()){
			set<int>::iterator it3=it1;
			it3--;
			long long hl=(*it1)-(*it3);
			hl*=(*it2)-p[i];
			q1+=hl;
		} 
		set<int>::iterator it4=it2;
		it4++;
		if(it4!=s.end()){
			long long hl=(*it4)-(*it2);
			hl*=p[i]-(*it1);
			q1+=hl;
		}
		ans+=q1*i;
		s.insert(p[i]); 
	}
	cout<<ans;
	return 0;
} 