// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)

#define REP(i,n) FOR(i,0,n)

#define ALL(v) (v).begin(),(v).end()

#define fi first

#define se second

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }

template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const ll INF = 1ll<<30;

const ll longINF = 1ll<<60;

const ll MOD = 1000000007;

const double EPS = 1e-9;

const bool debug = 0;

//---------------------------------//



template<typename T> struct BIT {

	vector<T> bit;

	int n;

	

	BIT() {}

	BIT(int n) : bit(vector<T>(n + 2, 0)), n(n) {}

	

	T sum(int i) {

		i++;

		T s = 0;

		while (i > 0) {

			s += bit[i];

			i -= i & -i;

		}

		return s;

	}

	

	void add(int i, T x) {

		i++;

		while (i <= n) {

			bit[i] += x;

			i += i & -i;

		}

	}

	

	T pquery(int i) {

		return sum(i) - sum(i - 1);

	}

	

	int lower_bound(T x) {

		int l = -1, r = bit.size();

		while (r - l > 1) {

			int m = (l + r) / 2;

			

			if (sum(m) >= x) r = m;

			else l = m;

		}

		if (r == bit.size()) r = -1;

		

		return r;

	}

};



int N;

ll P[112345];

BIT<int> bit(112345);



int main() {

	cin >> N;

	REP(i, N) scanf("%lld", P + i);

	

	vector<pll> v;

	REP(i, N) v.push_back(pll(P[i], i));

	sort(ALL(v), greater<pll>());

	

	ll ans = 0, cc = 0;

	bit.add(v[0].se, 1);

	FOR(i, 1, N) {

		pll cur = v[i];

		int p = cur.se;

		int l1 = bit.lower_bound(bit.sum(p));

		int l2 = bit.lower_bound(bit.sum(p) - 1);

		

		int r1 = bit.lower_bound(bit.sum(p) + 1);

		int r2 = bit.lower_bound(bit.sum(p) + 2);

		if (bit.sum(p) == 0) l1 = l2 = -1;

		if (l1 > -1 && bit.sum(l1) == 1) l2 = -1;

		if (r1 == -1) r1 = N;

		if (r2 == -1) r2 = N;

		

		

		ll pat = 0;

		pat += (l1 - l2) * (r1 - p);

		pat += (p - l1 - 1) * (r2 - r1);

		pat += r2 - r1;

		

		ans += cur.fi * pat;

		bit.add(p, 1);

		cc += pat;

	}

	cout << ans << endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)

#define REP(i,n) FOR(i,0,n)

#define ALL(v) (v).begin(),(v).end()

#define fi first

#define se second

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }

template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef long long ll;

typedef pair<int, int> pii;

const ll INF = 1ll<<30;

const ll longINF = 1ll<<60;

const ll MOD = 1000000007;

const bool debug = 0;

//---------------------------------//



int main() {

	int N;

	cin >> N;

	vector<int> P(N);

	REP(i, N) scanf("%d", P.begin() + i);

	

	vector<int> ord(N);

	REP(i, N) ord[i] = i;

	

	sort(ALL(ord), [&](int x, int y){

		return P[x] > P[y];

	});

	

	multiset<int> ss;

	REP(i, 2) {

		ss.insert(-1);

		ss.insert(N);

	}

	

	ll ans = 0;

	for (int i : ord) {

		auto it = ss.lower_bound(i);

		ll r1 = *it;

		ll r2 = *next(it, 1);

		ll l1 = *prev(it, 1);

		ll l2 = *prev(it, 2);

		

		ll pat = (l1 - l2) * (r1 - i) + (i - l1) * (r2 - r1);

		ans += pat * P[i];

		

		ss.insert(i);

	}

	

	cout << ans << endl;

	return 0;

}

// Fastest known solution for this problem: