//                             In The Name Of Allah
#include <bits/stdc++.h>
#define ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define ll long long
#define pb push_back
#define int long long
using namespace std;

const ll N = 1e6 + 100, OO = 1e10 + 10, M = 1e9 + 7, lg = 22;
typedef pair <int, int> pii;
int a[N];
pii seg[N], seg2[N];

void build(int c, int b, int e) {
	if(e - b == 1) {
		seg[c].ff = a[b];
		seg[c].ss = b;
		return;
	}
	int mid = (b + e) / 2;
	build(2 * c, b, mid);
	build(2 * c + 1, mid, e);
	seg[c].ff = max(seg[2 * c].ff, seg[2 * c + 1].ff);
	if(seg[c].ff == seg[2 * c + 1].ff)
		seg[c].ss = seg[2 * c + 1].ss;
	else
		seg[c].ss = seg[2 * c].ss;
}

int ans(int c, int b, int e, int q) {
	if(e - b == 1) 
		return seg[c].ss;
	int mid = (b + e) / 2;
	if(seg[2 * c + 1].ff > q) 
		return ans(2 * c + 1, mid, e, q);
	else
		return ans(2 * c, b, mid, q);
}

int get(int c, int b, int e, int l, int r, int q) {
	if(r - l <= 0)
		return -1;
	if(b == l && r == e) {
		if(seg[c].ff < q)
			return -1;
		return ans(c, b, e, q);
	}
	int mid = (b + e) / 2;
	if(r <= mid) 
		return get(2 * c, b, mid, l, r, q);
	if(l >= mid)
		return get(2 * c + 1, mid, e, l, r, q);
	int z = get(2 * c + 1, mid, e, mid, r, q);
	if(z == -1)
		return get(2 * c, b, mid, l, mid, q);
	else
		return z;
}

void build2(int c, int b, int e) {
	if(e - b == 1) {
		seg2[c].ff = a[b];
		seg2[c].ss = b;
		return;
	}
	int mid = (b + e) / 2;
	build2(2 * c, b, mid);
	build2(2 * c + 1, mid, e);
	seg2[c].ff = max(seg2[2 * c].ff, seg2[2 * c + 1].ff);
	if(seg2[c].ff == seg2[2 * c].ff)
		seg2[c].ss = seg2[2 * c].ss;
	else
		seg2[c].ss = seg2[2 * c + 1].ss;
}

int ans2(int c, int b, int e, int q) {
	if(e - b == 1) 
		return seg2[c].ss;
	int mid = (b + e) / 2;
	if(seg2[2 * c].ff > q) 
		return ans2(2 * c, b, mid, q);
	else
		return ans2(2 * c + 1, mid, e, q);
}

int get2(int c, int b, int e, int l, int r, int q) {
	if(r - l <= 0)
		return -1;
	if(b == l && r == e) {
		if(seg2[c].ff < q)
			return -1;
		return ans2(c, b, e, q);
	}
	int mid = (b + e) / 2;
	if(r <= mid) 
		return get2(2 * c, b, mid, l, r, q);
	if(l >= mid)
		return get2(2 * c + 1, mid, e, l, r, q);
	int z = get2(2 * c, b, mid, l, mid, q);
	if(z == -1)
		return get2(2 * c + 1, mid, e, mid, r, q);
	else
		return z;
}

int32_t main() {
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) 
		cin >> a[i];
	build(1, 0, n);	
	build2(1, 0, n);
	int ans = 0;
	for(int i = 0; i < n; i++) {
		int x = get(1, 0, n, 0, i, a[i]), x1 = -1;
		if(x == -1)
			x1 = -1;
		else
			x1 = get(1, 0, n, 0, x, a[i]);
		int y = get2(1, 0, n, i + 1, n, a[i]), y1 = 0;
		if(y == -1)
			y1 = -1;
		else
			y1 = get2(1, 0, n, y + 1, n, a[i]);
		if(x != -1) {
			if(y != -1) {
				int z = y - i;
				int k = x - x1;
				ans += z * k * a[i];
			}
			else {
				int z = n - i;
				int k = x - x1;
				ans += z * k * a[i];
			}
		}
		if(y != -1) {
			if(y1 == -1)
				y1 = n;
			if(x != -1) {
				int z = i - x;
				int k = y1 - y;
				ans += z * k * a[i];
			}
			else {
				int z = i + 1;
				int k = y1 - y;
				ans += z * k * a[i];
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 14592