#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 3e5 + 10, B = 1000, M = N / B + 2;
int n, p[N], pp[N], cnt[M][N * 2], tag[M], id[N], l[N], r[N], s[N];
int mn[M], mx[M], cnt1[N * 2], cnt2[N * 2];
ll ans;
signed main() {
	read(n);
	F(i, 1, n) read(p[i]), pp[p[i]] = i, id[i] = (i - 1) / B + 1, s[i] = i, cnt[id[i]][i + n] = 1;
	// F(j, 1, n)
	int tot = id[n];
	F(i, 1, tot) mn[i] = l[i] = (i - 1) * B + 1, mx[i] = r[i] = min(n, i * B);
	F(i, 1, n) {
		int x = pp[i];
		F(j, x, r[id[x]]) {
			// debug << s[j] << " " << s[j] + n << endl;
			cnt[id[x]][s[j] + n]--;
			cnt[id[x]][(s[j] -= 2) + n]++;
		}
		while (!cnt[id[x]][mx[id[x]] + n]) mx[id[x]]--;
		chkmin(mn[id[x]], mx[id[x]]);
		while (mn[id[x]] > -n && cnt[id[x]][mn[id[x]] - 1 + n]) {
			mn[id[x]]--;
			// debug << mn[id[x]] << " " << mn[id[x]] + n << " " << cnt[id[x]][mn[id[x]] + n] << endl;
		}
		F(j, id[x] + 1, tot) tag[j]--;
		int l1 = 1e9, r1 = -1e9;
		int l2 = 1e9, r2 = -1e9;
		F(j, l[id[x]], x - 1) {
			chkmin(l1, s[j] + tag[id[x]]);
			chkmax(r1, s[j] + tag[id[x]]);
		}
		F(j, 1, id[x] - 1) {
			chkmin(l1, mn[j] + tag[id[x]]);
			chkmax(r1, mx[j] + tag[id[x]]);
		}
		chkmin(l1, 0);
		chkmax(r1, 0);
		F(j, x, r[id[x]]) {
			chkmin(l2, s[j] + tag[id[x]]);
			chkmax(r2, s[j] + tag[id[x]]);
		}
		F(j, id[x] + 1, tot) {
			chkmin(l2, mn[j] + tag[id[x]]);
			chkmax(r2, mx[j] + tag[id[x]]);
		}
		int l = max(l1 - 1, l2), r = min(r1, r2 + 1);
		// debug << l1 << " " << r1 << endl;
		// debug << l2 << " " << r2 << endl;
		// debug << " -> " << i << " " << l << " " << r << endl;
		// F(i, l, r) cnt1[i + n] = cnt2[i + n] = 0;
		if (l <= 0 && 0 <= r) cnt1[n]++;
		F(j, ::l[id[x]], x - 1) {
			int v = s[j] + tag[id[x]];
			if (l <= v && v <= r) cnt1[v + n]++;
		}
		F(j, 1, id[x] - 1) {
			int L = max(l, mn[j]), R = min(r, mx[j]);
			F(k, L, R) cnt1[k + n] += cnt[j][k + n];
		}
		F(j, x, ::r[id[x]]) {
			int v = s[j] + tag[id[x]];
			if (l <= v && v <= r) cnt2[v + n]++;
		}
		F(j, id[x] + 1, tot) {
			int L = max(l, mn[j]), R = min(r, mx[j]);
			F(k, L, R) cnt2[k + n] += cnt[j][k + n];
		}
		// debug << l << " " << r << endl;
		F(t, l, r) {
			ans += (ll) i * cnt1[t + n] * cnt2[t + n];
			ans += (ll) i * cnt1[t + 1 + n] * cnt2[t + n];
			// debug << t << " " << cnt1[t + n] << " " << cnt2[t + n] << endl;
		}
		// debug << i << " " << ans << " " << l << " " << r << endl;
		F(i, l, r) cnt1[i + n] = cnt2[i + n] = 0;
	}
	cout << ans;
	return 0;
}