#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <stdio.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <list>
#include <utility>
#include <set>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <random>

using namespace std;

static const double EPS = 1e-9;
template<class T> bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
template<class T> void amin(T &a, T v) { if (a > v) a = v; }
template<class T> void amax(T &a, T v) { if (a < v) a = v; }
int ROUND(double x) { return (int)(x + 0.5); }
bool ISINT(double x) { return fabs(ROUND(x) - x) <= EPS; }
bool ISEQUAL(double x, double y) { return fabs(x - y) <= EPS * max(1.0, max(fabs(x), fabs(y))); }
double SQSUM(double x, double y) { return x * x + y * y; }
#define PI  (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0])) 
#define NG (-1)
#define BIG ((int)1e9+10)
#define BIGLL ((ll)4e18)
#define SZ(a) ((int)(a).size())
#define SQ(a) ((a)*(a))
typedef unsigned long long ull;
typedef long long ll;

using namespace std;
typedef long long ll;

// modint: mod 計算を int を扱うように扱える構造体
template<int MOD>
struct ModInt {
	long long val;
	constexpr ModInt(long long v = 0) noexcept : val(v % MOD) {
		if (val < 0) v += MOD;
	}
	constexpr int getmod() { return MOD; }
	constexpr ModInt operator - () const noexcept {
		return val ? MOD - val : 0;
	}
	constexpr ModInt operator + (const ModInt& r) const noexcept { return ModInt(*this) += r; }
	constexpr ModInt operator - (const ModInt& r) const noexcept { return ModInt(*this) -= r; }
	constexpr ModInt operator * (const ModInt& r) const noexcept { return ModInt(*this) *= r; }
	constexpr ModInt operator / (const ModInt& r) const noexcept { return ModInt(*this) /= r; }
	constexpr ModInt& operator += (const ModInt& r) noexcept {
		val += r.val;
		if (val >= MOD) val -= MOD;
		return *this;
	}
	constexpr ModInt& operator -= (const ModInt& r) noexcept {
		val -= r.val;
		if (val < 0) val += MOD;
		return *this;
	}
	constexpr ModInt& operator *= (const ModInt& r) noexcept {
		val = val * r.val % MOD;
		return *this;
	}
	constexpr ModInt& operator /= (const ModInt& r) noexcept {
		long long a = r.val, b = MOD, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		val = val * u % MOD;
		if (val < 0) val += MOD;
		return *this;
	}
	constexpr bool operator == (const ModInt& r) const noexcept {
		return this->val == r.val;
	}
	constexpr bool operator != (const ModInt& r) const noexcept {
		return this->val != r.val;
	}

	friend ostream& operator << (ostream &os, const ModInt<MOD>& x) noexcept {
		return os << x.val;
	}
	friend istream& operator >> (istream &is, ModInt<MOD>& x) noexcept {
		return is >> x.val;
	}
	static constexpr ModInt<MOD> modpow(const ModInt<MOD> &a, long long n) noexcept {
		if (n == 0) return 1;
		auto t = modpow(a, n / 2);
		t = t * t;
		if (n & 1) t = t * a;
		return t;
	}
};

template<class T>
vector<T> make_vector(int n, T t) {
	return vector<T>(n, t);
}

template<class ...Ts>
auto make_vector(int n, Ts ... ts) {
	return vector<decltype(make_vector(ts...))>(n, make_vector(ts...));
}

const int MOD = 1000000007;
using mint = ModInt<MOD>;

class RMQ
{
public:
	RMQ(int elems, int invalid)
	{
		mNumElements = elems + 1; // 差分をとる形で1個多いケース頻発するので
		mInvalid = invalid;
		init(mNumElements, mInvalid);
	}

	// k番目の値をとる
	int get(int k)
	{
		return dat[k + n - 1];	// 数列の0番目がdat[n-1]にくる。
	}

	// k番目に値vを足す
	void add(int k, int v)
	{
		update(k, get(k) + v);
	}

	void set(int k, int v)
	{
		int now = get(k);
		int adder = v - now;
		add(k, adder);
	}


	// k番目をaに
	void update(int k, int a)
	{
		k += n - 1;
		dat[k] = a;
		while (k>0)
		{
			k = (k - 1) / 2;
			dat[k] = op(dat[k * 2 + 1], dat[k * 2 + 2]);
		}
	}

	// 値がvである接点番号で一番小さいのを１個探す
	int getindex(int v, int k = 0)
	{
		if (k >= n - 1)
		{
			return k - (n - 1);
		}
		else if (dat[k * 2 + 1] == v)
		{
			return getindex(v, k * 2 + 1);
		}
		else if (dat[k * 2 + 2] == v)
		{
			return getindex(v, k * 2 + 2);
		}
		else
		{
			return -1;
		}
	}

	// [a,b)の最小値を求める（注 b以下じゃなくて、b未満だよ。）
	int getQuery(int a, int b)
	{
		return query(a, b, 0, 0, n);
	}

	// 全体の最小値を求める
	int getQueryAll()
	{
		return query(0, mNumElements, 0, 0, mNumElements);
	}

private:
	virtual int op(int a, int b) = 0;

	void init(int n_, int invalid)
	{
		// n_を2の累乗にする。
		n = 1;
		while (n<n_)
		{
			n *= 2;
		}

		dat.clear();
		dat.resize(2 * n - 1);
		fill(dat.begin(), dat.end(), invalid);
	}


	// ！[a,b)の最小値を求める（注 b以下じゃなくて、b未満だよ。）
	// ！外からはrmq_query(a,b,0,0,n)で呼ぶ
	// kが接点番号
	int query(int a, int b, int k, int l, int r)
	{
		if (r <= a || b <= l)
		{
			return mInvalid;
		}

		if (a <= l && r <= b)
		{
			return dat[k];
		}
		else
		{
			int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
			int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return op(vl, vr);
		}
	}

	int mInvalid;
	int mNumElements;	// 実際にユーザーが使う数
	int n;				// num_elementsを2の累乗にしたもの
	vector <int> dat;
};

class RMQMax : public RMQ
{
public:
	RMQMax(int elems) : RMQ(elems, -INT_MAX)
	{
	}

private:
	virtual int op(int a, int b)
	{
		return max(a, b);
	}
};

void binary(ll& ok, ll& ng, RMQMax& rmq, ll st, ll v)
{
	while (abs(ok - ng)>1)
	{
		ll mid = ok + (ng - ok) / 2LL; // ll 溢れ時は、lo+(hi-lo)/2LL;

		if (rmq.getQuery(st, mid) > v)
		{
			ok = mid;
		}
		else
		{
			ng = mid;
		} 
	}
}


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

	vector <int> place(N);
	for (int i = 0; i < N; ++i)
	{
		int tmp;
		cin >> tmp;
		tmp--;
		place[tmp] = i;
	}

	multiset <ll> st;
	st.insert(N);
	st.insert(N);
	st.insert(-1LL);
	st.insert(-1LL);

	ll ret = 0;
	for (int i = N-1; i >=0; --i)
	{
		multiset <ll>::iterator right1 = st.lower_bound(place[i]);
		// BEGIN CUT HERE
//		cerr << " i=" << i << " place[i]=" << place[i] << endl;
		// END CUT HERE

		multiset <ll>::iterator right2 = right1;
		right2++;
		multiset <ll>::iterator left1 = right1;
		left1--;
		multiset <ll>::iterator left2 = right1;
		left2--;
		left2--;

		ll r1 = *right1;
		ll r2 = *right2;
		ll l1 = *left1;
		ll l2 = *left2;

		// BEGIN CUT HERE
//		cerr << " l1=" << l1 << " l2=" << l2 << " r1=" << r1 << " r2=" << r2 << endl;
		// END CUT HERE



		ll numRange = 0;

		// 左に大きいやつが1つ、右に大きいやつが0つ
		numRange += abs(l2 - l1) * (abs(r1 - place[i]) ) ;

		// 右に大きいやつが1つ、左に大きいやつが0つ
		numRange += abs(r2 - r1) * (abs(l1 - place[i]) );


		ret += numRange * (i + 1);

		st.insert(place[i]);
	}

	cout << ret << endl;

	return 0;
}





Measured memory_bytes: 5376