#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N=300050;
const int S=300;
const int C=200;

int p[N],tmp[N],pos[N];
int bal[N],cnt[2*N];

const int M=2*N;
int ls[M],rs[M],tsz,root,sz[M];
void Add(int&c,int ss,int se,int qi,int f){
	if(!c)c=++tsz;
	sz[c]+=f;
	if(ss==se)return;
	int mid=ss+se>>1;
	if(qi<=mid)Add(ls[c],ss,mid,qi,f);
	else Add(rs[c],mid+1,se,qi,f);
}
int Get(int c,int ss,int se,int k){
	if(ss==se)return ss;
	int mid=ss+se>>1;
	if(sz[ls[c]]<k)return Get(rs[c],mid+1,se,k-sz[ls[c]]);
	return Get(ls[c],ss,mid,k);
}
int main(){
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++){
		scanf("%i",&p[i]);
		pos[p[i]]=i;
	}
	ll ans=0;
	for(int j=1;j<S;j++){
		for(int i=1;i<=n+j;i++){
			if(i-j>=1)Add(root,1,n,p[i-j],-1);
			if(i<=n)Add(root,1,n,p[i],1);
			if(i>=j && i<=n){
				ans+=Get(root,1,n,(j+1)/2);
			}
		}
	}
	for(int mid=n/2-C;mid<=n/2+C;mid++){
		if(mid>=1 && mid<=n){
			for(int i=1;i<=n;i++){
				bal[i]=bal[i-1]+(p[i]>mid)-(p[i]<mid);
				if(i-S>=0 && i-S<pos[mid])cnt[N+bal[i-S]]++;
				if(i>=pos[mid]){
					ans+=(ll)(cnt[N+bal[i]]+cnt[N+bal[i]-1])*mid;
				}
			}
			for(int i=0;i<=n;i++)cnt[N+bal[i]]=0;
		}
	}
	printf("%lld\n",ans);
	return 0;
}