#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


int n, p[300030];

int pool1[1000030], pool2[1000030], pool3[1000030], pool4[1000030];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	cin>>n;

	for(int i=1;i<=n;i++) {
		cin>>p[i];
	}

	int *cc1 = pool1 + 500000, *vis1 = pool2+500000, *cc2 = pool3 + 500000, *vis2 = pool4+500000;

	ll ans = 0;
	for(int i=1;i<=n;i++) {
		double balance = abs(1.0* (p[i] - n/2) / n);

		int lim = 1000;
		if(balance < 0.4) {
			lim = 2000;
		}
		if(balance < 0.2) {
			lim = 4000;
		}
		if(balance < 0.1) {
			lim = 80000;
		}
		if(balance < 0.06) {
			lim = 10000;
		}
		if(balance < 0.03) {
			lim = 20000;
		}
		if(balance < 0.02) {
			lim = 30000;
		}
		if(balance < 0.01) {
			lim = 50000;
		}
		if(balance < 0.005) {
			lim = 30000000;
		}
		//cout<<"i: "<<i<<endl;

		int cnt = 0;
		for(int j=i;j>=max(1, i-lim);j--) {
			if(p[j] < p[i]) cnt -= 1;
			else cnt += 1;
			int *vis = vis1, *cc = cc1;
			if(j%2 == 0) {
				vis = vis2;
				cc = cc2;
			}
			if(vis[cnt] != i) {
				vis[cnt] = i;
				cc[cnt] = 0;
			}
			cc[cnt] += 1;
		}
		cnt = 0;
		for(int j=i; j<=min(n, i+lim);j++) {
			int *v1 = vis1, *c1 = cc1, *v2 = vis2, *c2 = cc2;
			if(j%2 == 0) {
				swap(v1, v2);
				swap(c1, c2);
			}
			if(v1[cnt+1] == i){
				ans += 1ll*c1[cnt+1] * p[i];
				//cout<<j<<" 1: "<<c1[cnt+1]<<endl;
			}
			if(v2[cnt+2] == i){
				ans += 1ll*c2[cnt+2] * p[i];
				//cout<<j<<" 2: "<<c2[cnt+2]<<endl;
			}
			if(p[j+1] < p[i]) cnt += 1;
			else cnt -= 1;
		}
	}
	cout<<ans<<endl;
	return 0;
}