#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#define N 100005
#define F first
#define S second
using namespace std;

typedef long long ll;
ll n, sum;
pair<ll, ll> a[N];
multiset<ll> s;
int main()
{
	ll i, l1, l2, r1, r2;
	multiset<ll>::iterator it;
	cin >> n;
	for (i = 0; i < n; i++) {
		scanf("%lld", &a[i].F);
		a[i].S = i + 1;
	}
	sort(a, a + n, greater<pair<ll, ll> >());
	s.insert(0); s.insert(0);
	s.insert(n + 1); s.insert(n + 1);
	for (i = 0; i < n; i++) {
		it = s.lower_bound(a[i].S);
		r1 = *it;
		r2 = *next(it);
		l1 = *prev(it);
		l2 = *prev(prev(it));
        sum += ((a[i].S - l1) * (r2 - r1) + (l1 - l2) * (r1 - a[i].S)) * a[i].F;
        s.insert(a[i].S);
	}
    cout << sum << endl;
    return 0;
}