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

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 *cc = pool1 + 500000;

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

		int lim = 300;
		if(balance < 0.3) {
			lim = 500;
		}
		if(balance < 0.2) {
			lim = 750;
		}
		if(balance < 0.1) {
			lim = 1500;
		}
		if(balance < 0.06) {
			lim = 4500;
		}
		if(balance < 0.03) {
			lim = 12000;
		}
		if(balance < 0.02) {
			lim = 20000;
		}
		if(balance < 0.01) {
			lim = 30000;
		}
		if(balance < 0.007) {
			lim = 60000;
		}
		if(balance < 0.005) {
			lim = 100000;
		}
		if(balance < 0.003) {
			lim = 140000;
		}
		if(balance < 0.002) {
			lim = 250000;
		}
		if(balance < 0.0015) {
			lim = 300000;
		}
		lim = min(lim, max(i, n-i) + 10);
		int cnt = 0, pc = p[i];
		int j = i;
		for(;j>=max(1,i-lim);j-=8) {
			cnt += 2 * (p[j] >= pc) - 1;
			cc[cnt]++;
			cnt += 2 * (p[j-1] >= pc) - 1;
			cc[cnt]++;
			cnt += 2 * (p[j-2] >= pc) - 1;
			cc[cnt]++;
			cnt += 2 * (p[j-3] >= pc) - 1;
			cc[cnt]++;
			cnt += 2 * (p[j-4] >= pc) - 1;
			cc[cnt]++;
			cnt += 2 * (p[j-5] >= pc) - 1;
			cc[cnt]++;
			cnt += 2 * (p[j-6] >= pc) - 1;
			cc[cnt]++;
			cnt += 2 * (p[j-7] >= pc) - 1;
			cc[cnt]++;
		}
		for(;j>=max(1,i-lim);j--) {
			cnt += 2 * (p[j] >= pc) - 1;
			cc[cnt]++;
		}
		cnt = 0;
		j=i;
		for(; j+4<=min(n, i+lim);j+=8) {
			ans += 1ll*(cc[cnt+1]+cc[cnt+2]) * pc;
			cnt += 2 * (p[j+1] < pc) - 1;
			ans += 1ll*(cc[cnt+1]+cc[cnt+2]) * pc;
			cnt += 2 * (p[j+2] < pc) - 1;
			ans += 1ll*(cc[cnt+1]+cc[cnt+2]) * pc;
			cnt += 2 * (p[j+3] < pc) - 1;
			ans += 1ll*(cc[cnt+1]+cc[cnt+2]) * pc;
			cnt += 2 * (p[j+4] < pc) - 1;
			ans += 1ll*(cc[cnt+1]+cc[cnt+2]) * pc;
			cnt += 2 * (p[j+5] < pc) - 1;
			ans += 1ll*(cc[cnt+1]+cc[cnt+2]) * pc;
			cnt += 2 * (p[j+6] < pc) - 1;
			ans += 1ll*(cc[cnt+1]+cc[cnt+2]) * pc;
			cnt += 2 * (p[j+7] < pc) - 1;
			ans += 1ll*(cc[cnt+1]+cc[cnt+2]) * pc;
			cnt += 2 * (p[j+8] < pc) - 1;
		}
		for(; j<=min(n, i+lim);j++) {
			ans += 1ll*(cc[cnt+1]+cc[cnt+2]) * pc;
			cnt += 2 * (p[j+1] < pc) - 1;
		}
		memset(cc-lim-10, 0, sizeof(int) * (2*lim+21));
	}
	cout<<ans<<endl;
	return 0;
}