#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;

template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}

int n, p[300030];

int pool1[1000030], pool3[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, *cc2 = pool3 + 500000;

	ll ans = 0;
	for(int i=1;i<=n;i++) {
		double balance = abs(1.0* (p[i] - (n+1)/2.0) / n);
		int lim = max(300, int(10.0/(1e-9+balance*balance)));
		// int lim = 300;
		lim = min(lim, max(i, n-i) + 10);
		int cnt = 0;
		for(int j=i;j>=max(1, i-lim);j--) {
			if(p[j] < p[i]) cnt -= 1;
			else cnt += 1;
			int *cc = j%2==0 ? cc2 : cc1;
			cc[cnt] += 1;
		}
		cnt = 0;
		for(int j=i; j<=min(n, i+lim);j++) {
			int *c1 = cc1, *c2 = cc2;
			if(j%2 == 0) {
				swap(c1, c2);
			}
			ans += 1ll*c1[cnt+1] * p[i];
			ans += 1ll*c2[cnt+2] * p[i];
			if(p[j+1] < p[i]) cnt += 1;
			else cnt -= 1;
		}
		memset(cc1-lim-10, 0, sizeof(int) * (2*lim+21));
		memset(cc2-lim-10, 0, sizeof(int) * (2*lim+21));
	}
	cout<<ans<<endl;
	return 0;
}