#pragma GCC optimize("O3")

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <string>
#include <assert.h>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <random>
#include <cmath>
#include <chrono>
#include <bitset>

#define ld long double
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

#define int long long
using namespace std;

const int INF = 2e18;
const int MOD = 1e9 + 7;
const int MB = 20;

struct SegmentTree {
	vector<int> mn, idMin, mx, idMax;
	int n;
	void build(int x) {
		n = x;
		mn.resize(n << 2);
		fill(all(mn), INF);
		idMin.resize(n << 2);
		mx.resize(n << 2);
		fill(all(mx), -1);
		idMax.resize(n << 2);
		buildTree(1, 0, n);
	}

	void update(int v, int vl, int vr) {
		if (mn[vl] < mn[vr]) {
			mn[v] = mn[vl];
			idMin[v] = idMin[vl];
		}
		else {
			mn[v] = mn[vr];
			idMin[v] = idMin[vr];
		}

		if (mx[vl] > mx[vr]) {
			mx[v] = mx[vl];
			idMax[v] = idMax[vl];
		}
		else {
			mx[v] = mx[vr];
			idMax[v] = idMax[vr];
		}
	}

	void buildTree(int v, int l, int r) {
		if (l + 1 == r) {
			idMin[v] = l;
			idMax[v] = l;
			return;
		}

		int m = (l + r) >> 1;
		int vl = v << 1;
		int vr = vl + 1;

		buildTree(vl, l, m);
		buildTree(vr, m, r);
		
		update(v, vl, vr);
	}

	int id, value;
	void update(int i, int v) {
		id = i;
		value = v;
		updateTree(1, 0, n);
	}

	void updateTree(int v, int l, int r) {
		if (l + 1== r) {
			mn[v] = mx[v] = value;
			return;
		}

		int m = (l + r) >> 1;
		int vl = v << 1;
		int vr = vl + 1;

		if (id < m) updateTree(vl, l, m);
		else updateTree(vr, m, r);
		
		update(v, vl, vr);
	}

	int res, start, end;
	bool one;
	int getMin(int l, int r) {
		res = INF;
		one = false;
		id = 0;
		start = l;
		end = r + 1;
		getTree(1, 0, n);
		return id;
	}

	int getMax(int l, int r) {
		res = -1;
		one = true;
		id = 0;
		start = l;
		end = r + 1;
		getTree(1, 0, n);
		return id;
	}

	void getTree(int v, int l, int r) {
		if (start <= l && r <= end) {
			if (one && res < mx[v]) {
				res = mx[v];
				id = idMax[v];
			}
			else if (!one && res > mn[v]) {
				res = mn[v];
				id = idMin[v];
			}
			return;
		}

		int m = (l + r) >> 1;
		int vl = v << 1;
		int vr = vl + 1;

		if (start < m) getTree(vl, l, m);
		if (m < end) getTree(vr, m, r);
	}
};

void solve() {
	int n;
	cin >> n;
	vector<int> a(n), pos(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
		pos[a[i]] = i;
	}

	SegmentTree tree;
	tree.build(n);

	vector<int> left1(n, -1), left2(n, -1), right1(n, n), right2(n, n);

	int ans = 0;
	for (int i = 0; i < n; i++) {
		int id = tree.getMax(a[i], n - 1);
		if (pos[id] < i && id > a[i]) {
			tree.update(id, -1);
			left1[a[i]] = pos[id];
			int id1 = tree.getMax(a[i], n - 1);
			if (pos[id1] < pos[id] && id1 > a[i]) {
				left2[a[i]] = pos[id1];
			}
			tree.update(id, pos[id]);
		}
		tree.update(a[i], i);
	}

	tree.build(n);
	for (int i = n - 1; i >= 0; i--) {
		int id = tree.getMin(a[i], n - 1);
		if (pos[id] > i && id > a[i]) {
			right1[a[i]] = pos[id];
			tree.update(id, INF);
			int id1 = tree.getMin(a[i], n - 1);
			if (pos[id1] > pos[id] && id1 > a[i]) {
				right2[a[i]] = pos[id1];
			}
			tree.update(id, pos[id]);
		}
		tree.update(a[i], i);
	}

	for (int i = 0; i < n; i++) {
		if (left1[i] != -1) ans += (i + 1) * (left1[i] - left2[i]) * (right1[i] - pos[i]);
		if (right1[i] != n) ans += (i + 1) * (right2[i] - right1[i]) * (pos[i] - left1[i]);
	}

	cout << ans;
}
signed main() {
	/*
	freopen("search.in", "r", stdin);
	freopen("search.out", "w", stdout);
	*/
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(12);
	solve();
}

Measured memory_bytes: 17536