#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<Int> idx(N + 1);
	for (int i = 0; i < N; ++i) {
		int p;
		cin >> p;
		idx[p] = i;
	}

	multiset<Int> st;
	st.insert(-1);
	st.insert(-1);
	st.insert(N);
	st.insert(N);
	Int ans = 0;
	for (Int i = N; i > 0; --i) {
		auto r = st.upper_bound(idx[i]);
		Int r1 = *r;
		Int r2 = *next(r);
		auto l = prev(st.lower_bound(idx[i]));
		Int l1 = *l;
		Int l2 = *prev(l);

		ans += i * ((l1 - l2)*(r1 - idx[i]) + (idx[i] - l1)*(r2 - r1));
		st.insert(idx[i]);
	}
	cout << ans << endl;

	return 0;
}
