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

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

int p[N],tmp[N],pos[N];
int bal[N],cnt[2*N];
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 i=1;i<=n;i++){
		for(int j=1;j<S;j++){
			if(i+j-1<=n){
				for(int z=0;z<j;z++){
					tmp[z]=p[i+z];
				}
				nth_element(tmp,tmp+(j-1)/2,tmp+j);
				ans+=tmp[(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;
}