#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")

int n;
int a[300300];
long long ans=0;
//unordered_map<int,int> l;
int l[1001001];
double getl(double p) {
	if(abs(0.5-p)<1e-9) return 10*n;
	else return min(10.0*n,log(5e-7) / (log(2)+log(p)/2+log(1-p)/2));
}
void solve(int x) {
	int mxl=getl(1.0*a[x]/n);
	l[0]=1;
	int ll=max(1,x-mxl),rr=min(n,x+mxl);
	for(int i=x-1,tmp=n;i>=ll;--i) {
		if(a[i]<a[x]) --tmp;
		else ++tmp;
		l[tmp]=l[tmp]+1;
	}
	int res=0;
	res+=l[0]+l[1];
	for(int i=x+1,tmp=n;i<=rr;++i) {
		if(a[i]<a[x]) ++tmp;
		else --tmp;
		res+=l[tmp]+l[tmp+1];
	}
	ans+=1ll*res*a[x];
	l[0]=0;
	for(int i=x-1,tmp=n;i>=ll;--i) {
		if(a[i]<a[x]) --tmp;
		else ++tmp;
		l[tmp]=0;
	}
}
int main() {
	scanf("%d",&n);
//	n=300000;
	for(int i=1;i<=n;++i) {
		scanf("%d",&a[i]);
//		a[i]=i;
	}
//	random_shuffle(a+1,a+n+1);
	for(int i=1;i<=n;++i) {
		solve(i);
//		if(i%10000==0) cout<<i<<endl;
	}
	printf("%lld\n",ans);
	return 0;
}
/*
4
1 4 2 3
*/