#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#include <utility>
#include <set>
#include <stack>
#include <deque>
#include <ctime>
#include <random>
#include <cassert>
#include <cmath>
#include <climits>
#include <queue>
#include <cstring>
#include <bitset>
#include <iomanip>
#include <chrono>

/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("popcnt")
#pragma GCC target("avx2")
*/


#ifdef LOCAL
	#define dbg(x) cout << #x << " : " << x << endl;
#else 
	#define dbg(x)
#endif

#define fi(a,b) for (int i=a;i<b;i++)
#define fj(a,b) for (int j=a;j<b;j++)
#define fk(a,b) for (int k=a;k<b;k++)
#define fi1(a,b) for (int i=a-1;i>=b;i--)
#define fj1(a,b) for (int j=a-1;j>=b;j--)
#define fk1(a,b) for (int k=a-1;k>=b;k--)
#define fx(x,a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

template<typename T1, typename T2>inline void mine(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, T2 y) { if (x < y) x = y; }

ostream& operator << (ostream &a, const vector<int> &b) {
    for (auto k : b) cout << k << ' ';
    return a;
}


typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;



const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 100010;
const double EPS = 1e-9;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int n;
int t[4 * MX];
int p[MX];

void build(int v, int l, int r) {
	if (l + 1 == r) 
		t[v] = p[l];
	else {
		int m = (l + r) >> 1;
		build(2 * v, l, m);
		build(2 *v + 1, m, r);
		t[v] = max(t[2 * v], t[2 * v + 1]);
	}
}


int leftmore(int v, int x, int l, int r, int cl, int cr) {
	if (t[v] <= x || cl >= r || cr <= l)
		return n;
	if (cl + 1 == cr)
		return cl;
	
	int m = (cl + cr) >> 1;
	if (cl >= l && cr <= r) {
		if (t[2 * v] > x)
			return leftmore(2 * v, x, l, r, cl, m);
		else
			return leftmore(2 * v + 1, x, l, r, m, cr);
	} else {
		int res1 = leftmore(2 * v, x, l, r, cl, m);
		if (res1 != n)
			return res1;
		return leftmore(2 * v + 1, x, l, r, m, cr);
	}
}


int rightmore(int v, int x, int l, int r, int cl, int cr) {
	if (t[v] <= x || cl >= r || cr <= l)
		return -1;
	if (cl + 1 == cr)
		return cl;

	int m = (cl + cr) >> 1;
	if (cl >= l && cr <= r) {
		if (t[2 * v + 1] > x)
			return rightmore(2 * v + 1, x, l, r, m, cr);
		else
			return rightmore(2 * v, x, l, r, cl, m);
	} else {
		int res1 = rightmore(2 * v + 1, x, l, r, m, cr);
		if (res1 != -1)
			return res1;
		return rightmore(2 * v, x, l, r, cl, m);
	}
}


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
   	
   	cin >> n;
   	fi(0, n) {
   		cin >> p[i];
   	}
   	build(1, 0, n);
   	ll res = 0;
   	fi(0, n) {
   		int l1 = rightmore(1, p[i], 0, i, 0, n);
   		int l2 = rightmore(1, p[i], 0, l1, 0, n);
   		int r1 = leftmore(1, p[i], i + 1, n, 0, n);
   		int r2 = leftmore(1, p[i], r1 + 1, n, 0, n);
   		res += 1ll * (l1 - l2) * (r1 - i) * p[i];
   		res += 1ll * (r2 - r1) * (i - l1) * p[i];
   	}
   	cout << res << '\n';
}

Measured memory_bytes: 1664