#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return x;
}
int n;
int a[300300];
long long ans=0;
double getl(double p) {
	if(abs(0.5-p)<1e-9) return 1e6;
	else return min(1e6,log(5e-7) / (log(2)+log(p)/2+log(1-p)/2));
}
int tmp1[600600],tmp2[60600];
void solve(int x) {
	int mxl=getl(1.0*a[x]/n);
	int ll=max(1,x-mxl),rr=min(n,x+mxl);
	tmp1[ll-1]=rr-ll+1;
	#pragma unroll 8
    for (int k=ll;k<=rr;++k) {
		tmp1[k]=tmp1[k-1]+(a[k]>a[x] ? 1 : -1);
    }
    #pragma unroll 8
    for (int k=ll;k<=x;++k) {
		++tmp2[tmp1[k-1]];
    }
	long long res=0;
	#pragma unroll 8
    for (int k=x;k<=rr;++k) {
		res+=tmp2[tmp1[k]]+tmp2[tmp1[k]+1];
    }
    ans+=1ll*a[x]*res;
    #pragma unroll 8
    for (int k=ll;k<=x;++k) {
		tmp2[tmp1[k-1]]=0;
    }
}
int main() {
//	scanf("%d",&n);
	n=read();
	for(int i=1;i<=n;++i) {
//		scanf("%d",&a[i]);
		a[i]=read();
	}
//	random_shuffle(a+1,a+n+1);
	for(int i=1;i<=n;++i) {
		solve(i);
	}
	printf("%lld\n",ans);
	return 0;
}
/*
4
1 4 2 3
*/