#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MAXN = 3e5 + 100;
array<int, 2> tree[MAXN * 4];
int add[MAXN * 4];

void pull(int v) {
	tree[v][0] = min(tree[v * 2][0], tree[v * 2 + 1][0]);
	tree[v][1] = max(tree[v * 2][1], tree[v * 2 + 1][1]);
	tree[v][0] += add[v];
	tree[v][1] += add[v];
}

int bal[MAXN];

void build(int v, int vl, int vr) {
	add[v] = 0;
	if (vr - vl == 1) {
		tree[v][0] = tree[v][1] = bal[vl];
		return;
	}
	int vm = (vl + vr) / 2;
	build(v * 2, vl, vm);
	build(v * 2 + 1, vm, vr);
	pull(v);
}

void update(int v, int vl, int vr, int l, int r, int val) {
	if (l >= vr || r <= vl) return;
	if (l <= vl && r >= vr) {
		add[v] += val;
		tree[v][0] += val;
		tree[v][1] += val;
		return;
	}
	int vm = (vl + vr) / 2;
	update(v * 2, vl, vm, l, r, val);
	update(v * 2 + 1, vm, vr, l, r, val);
	pull(v);
}

array<int, 2> get(int v, int vl, int vr, int l, int r) {
	if (l >= vr || r <= vl) return {MAXN * 2, -MAXN * 2};
	if (l <= vl && r >= vr) return tree[v];
	int vm = (vl + vr) / 2;
	auto res1 = get(v * 2, vl, vm, l, r);
	auto res2 = get(v * 2 + 1, vm, vr, l, r);
	array<int, 2> res = {min(res1[0], res2[0]), max(res1[1], res2[1])};
	res[0] += add[v];
	res[1] += add[v];
	return res;
}

int get_last_low(int v, int vl, int vr, int val) {
	if (tree[v][0] > val) return -1;
	if (vr - vl == 1) return vl;
	val -= add[v];
	int vm = (vl + vr) / 2;
	int res = get_last_low(v * 2 + 1, vm, vr, val);
	if (res == -1) return get_last_low(v * 2, vl, vm, val);
	return res;
}

int get_last_big(int v, int vl, int vr, int val) {
	if (tree[v][1] < val) return -1;
	if (vr - vl == 1) return vl;
	val -= add[v];
	int vm = (vl + vr) / 2;
	int res = get_last_big(v * 2 + 1, vm, vr, val);
	if (res == -1) return get_last_big(v * 2, vl, vm, val);
	return res;
}

int get_first_low(int v, int vl, int vr, int val) {
	if (tree[v][0] > val) return -1;
	if (vr - vl == 1) return vl;
	val -= add[v];
	int vm = (vl + vr) / 2;
	int res = get_first_low(v * 2, vl, vm, val);
	if (res == -1) return get_first_low(v * 2 + 1, vm, vr, val);
	return res;
}

int get_first_big(int v, int vl, int vr, int val) {
	if (tree[v][1] < val) return -1;
	if (vr - vl == 1) return vl;
	val -= add[v];
	int vm = (vl + vr) / 2;
	int res = get_first_big(v * 2, vl, vm, val);
	if (res == -1) return get_first_big(v * 2 + 1, vm, vr, val);
	return res;
}

void load(int v, int vl, int vr, int l, int r, int a = 0) {
	if (l >= vr || r <= vl) return;
	if (vr - vl == 1) {
		bal[vl] = tree[v][0] + a;
		return;
	}
	int vm = (vl + vr) / 2;
	a += add[v];
	load(v * 2, vl, vm, l, r, a);
	load(v * 2 + 1, vm, vr, l, r, a);
}

int pos[MAXN];

int cnt[MAXN * 2], id[MAXN * 2];
int cur_id = 0;

void add_cnt(int i) {
	if (id[i] != cur_id) {
		id[i] = cur_id;
		cnt[i] = 0;
	}
	++cnt[i];
}

int get_cnt(int i) {
	if (id[i] != cur_id) {
		id[i] = cur_id;
		cnt[i] = 0;
	}
	return cnt[i];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	vector<int> p(n);
	/**iota(p.begin(), p.end(), 1);
	mt19937_64 rnd(1);
	shuffle(p.begin(), p.end(), rnd);*/
	for (int i = 0; i < n; ++i) {
		cin >> p[i];
		pos[p[i]] = i;
	}
	bal[0] = n;
	for (int i = 0; i < n; ++i) {
		bal[i + 1] = bal[i] - 1;
	}
	build(1, 0, n + 1);
	int64_t ans = 0;
	for (int i = n; i > 0; --i) {
		int V = i;
		if (i < n) {
			update(1, 0, n + 1, pos[i + 1] + 1, n + 1, 1);
		}
		update(1, 0, n + 1, pos[i] + 1, n + 1, 1);
		auto res = get(1, 0, n, 0, pos[i] + 1);
		int mx = res[1], mn = res[0];
		/// cerr << mx << " " << mn << endl;
		int rgh = n;
		int x = get_last_low(1, 0, n + 1, mx + 1);
		/// cerr << x << endl;
		if (x != -1) {
			rgh = min(rgh, x);
		}
		x = get_last_big(1, 0, n + 1, mn);
		/// cerr << x << endl;
		if (x != -1) {
			rgh = min(rgh, x);
		}
		int lft = 0;
		res = get(1, 0, n, pos[i] + 1, n + 1);
		mx = res[1], mn = res[0];
		x = get_first_low(1, 0, n + 1, mx);
		if (x != -1) {
			lft = max(lft, x);
		}
		x = get_first_big(1, 0, n + 1, mn - 1);
		if (x != -1) {
			lft = max(lft, x);
		}

		/// cerr << V << ": " << lft << " " << rgh << endl;

		load(1, 0, n + 1, lft, rgh + 1);
		++cur_id;
		for (int t = pos[i] + 1; t <= rgh; ++t) {
			add_cnt(bal[t]);
		}
		for (int t = lft; t <= pos[i]; ++t) {
			ans += 1ll * get_cnt(bal[t]) * V;
			ans += 1ll * get_cnt(bal[t] + 1) * V;
		}
		/// cerr << "ans: " << ans << endl;
	}
	cout << ans << "\n";
	return 0;
}