#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5;
int a[MAXN],w[MAXN<<1];
int f(double e) { return max(15./e/e,100.); }
signed main() {
	int n; ll ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=n;++i) {
		int rd=2*i==n?n:f(abs(0.5-1.*i/n));
		int l=max(1,i-rd+1),r=min(n,i+rd-1),len=l-i+1;
		for(int j=i,s=n;j>=l;--j) s+=a[j]>a[i]?1:-1,++w[s];
		for(int j=i,s=n+1;j<=r;++j) s+=a[j]>a[i]?1:-1,ans+=1ll*a[i]*(w[2*n-s]+w[2*n-1-s]);
		fill(w+n-len,w+n+len+1,0);
	}
	printf("%lld\n",ans);
	return 0;
}