#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[600600];
int main() {
	scanf("%d",&n);
//	n=read();
	for(int i=1;i<=n;++i) {
		scanf("%d",&a[i]);
//		a[i]=read();
	}
	for(int x=1;x<=n;++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;
	    for (int k=ll;k<=rr;++k) {
			tmp1[k]=tmp1[k-1]+(a[k]>a[x] ? 1 : -1);
	    }
	    for (int k=ll;k<=x;++k) {
			++tmp2[tmp1[k-1]];
	    }
		long long res=0;
	    for (int k=x;k<=rr;++k) {
			res+=tmp2[tmp1[k]]+tmp2[tmp1[k]+1];
	    }
	    ans+=1ll*a[x]*res;
	    for (int k=ll;k<=x;++k) {
			tmp2[tmp1[k-1]]=0;
	    }
	}
	printf("%lld\n",ans);
	return 0;
}