#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")

int n;
int a[300300];
long long ans=0;
//unordered_map<int,int> l;
struct likemap {
	int ma[10000];
	int& operator [] (int x) {
		return ma[x+3000];
	}
}l;
long long upperdiv(long long a,long long b) {
	return (a+b-1)/b;
}

void solve(int x) {
//	l.clear();
	int mxl=6*sqrt(upperdiv(1ll*a[x]*(n-a[x]),1ll*n))+600;
//	cout<<mxl<<'?'<<endl;
	l[0]=1;
	for(int i=x-1,tmp=0;i>=1 && (x-i)<=mxl;--i) {
		if(a[i]<a[x]) --tmp;
		else ++tmp;
		if(!l[tmp]) l[tmp]=1;
		else ++l[tmp];
	}
	ans+=1ll*l[0]*a[x]+1ll*l[1]*a[x];
	for(int i=x+1,tmp=0;i<=n && (i-x)<=mxl;++i) {
		if(a[i]<a[x]) --tmp;
		else ++tmp;
		ans+=1ll*l[-tmp]*a[x]+1ll*l[-tmp+1]*a[x];
	}
	l[0]=0;
	for(int i=x-1,tmp=0;i>=1 && (x-i)<=mxl;--i) {
		if(a[i]<a[x]) --tmp;
		else ++tmp;
		l[tmp]=0;
	}
}
int main() {
	scanf("%d",&n);
//	n=300000;
	for(int i=1;i<=n;++i) {
		scanf("%d",&a[i]);
//		a[i]=i;
	}
//	random_shuffle(a+1,a+n+1);
	for(int i=1;i<=n;++i) {
		solve(i);
//		if(i%10000==0) cout<<i<<endl;
	}
	printf("%lld\n",ans);
	return 0;
}
/*
4
1 4 2 3
*/