#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

using namespace std;

vector<int> random_permutation(int n){
	random_device seed_gen;
	mt19937 engine(seed_gen());
	vector<int> p(n);
	iota(p.begin(), p.end(), 1);
	shuffle(p.begin(), p.end(), engine);
	return p;
}

ll naive(int n, vector<int> p){
	ll ans = 0;
	rep(i,0,n){
		priority_queue<int, vector<int>, greater<int>> larger;
		priority_queue<int> smaller;
		rep(j,i,n){
			if (smaller.empty()){
				smaller.push(p[j]);
			}else if(larger.empty()){
				smaller.push(p[j]);
			}else if(larger.top() > p[j]){
				smaller.push(p[j]);
			}else{
				larger.push(p[j]);
			}
			while ((int)smaller.size() < (int)larger.size()){
				smaller.push(larger.top());
				larger.pop();
			}
			while ((int)smaller.size() > (int)larger.size() + 1){
				larger.push(smaller.top());
				smaller.pop();
			}
			ans += smaller.top();
		}
	}
	return ans;
}

const int mx = 1000;
const int mx_sub1 = 500;
const int mx_sub2 = 300;

ll fast(int n, vector<int> p){
	ll ans = 0;
	vector<int> left(2 * mx + 1);
	vector<int> right(2 * mx + 1);
	rep(i,0,n){
		fill(left.begin(), left.end(), 0);
		fill(right.begin(), right.end(), 0);
		int targ = p[i];
		{
			int cnt = mx;
			left[cnt]++;
			rrep(j,0,i){
				if (targ < p[j]) cnt--;
				else cnt++;
				if (abs(cnt - mx) > mx) break;
				left[cnt]++;
			}
		}
		{
			int cnt = mx + 1;
			right[cnt]++;
			rep(j,i+1,n){
				if (targ < p[j]) cnt--;
				else cnt++;
				if (abs(cnt - mx) > mx) break;
				right[cnt]++;
			}
		}
		ll var = 0;
		rep(j, 0, 2 * mx){
			var += (ll)right[2 * mx - j] * (left[j] + left[j + 1]);
		}
		ans += var * targ;
	}
	return ans;
}


ll fast2(int n, vector<int> p){
	ll ans = 0;
	vector<int> left(2 * mx + 1);
	vector<int> right(2 * mx + 1);
	vector<int> a(n, +1);
	
	vector<int> q(n);
	rep(i,0,n){
		q[p[i] - 1] = i;
	}
	reverse(q.begin(), q.end());

	for (int i: q){

		int targ = mx;
		if (min(n + 1 - p[i], p[i]) < n / 8){
			targ = mx_sub2;
		}else if (min(n + 1 - p[i], p[i]) < n / 4){
			targ = mx_sub1;
		}

		fill(left.begin() + mx - targ, left.begin() + mx + targ, 0);
		fill(right.begin() + mx - targ, right.begin() + mx + targ, 0);

		{
			int cnt = mx;
			left[cnt]++;
			rrep(j,0,i){
				cnt += a[j];
				if (abs(cnt - mx) > targ) break;
				left[cnt]++;
			}
		}

		{
			int cnt = mx + 1;
			right[cnt]++;
			rep(j,i+1,n){
				cnt += a[j];
				if (abs(cnt - mx) > targ) break;
				right[cnt]++;
			}
		}

		ll var = 0;
		rep(j, mx - targ, mx + targ - 1){
			var += (ll)right[2 * mx - j] * (left[j] + left[j + 1]);
		}
		ans += var * p[i];
		a[i] = -1;
	}

	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	//*
	int n; cin >> n;
	vector<int> p(n);
	rep(i,0,n){
		cin >> p[i];
	}
	//*/

	/*
	int n = 300000;
	vector<int> p = random_permutation(n);
	//*/
	
	//cout << naive(n, p) << endl;
	cout << fast2(n, p) << endl;
	//cout << fast(n, p) << endl;
}