#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#pragma GCC optimize(2)
#define boo(i) bitset<i>
#define ri register int
#define rll register long long
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
#define max_(i,j) (i<j?j:i)
#define min_(i,j) (i<j?i:j)
#define abs_(x) (x>0?x:(-x))
using namespace std;
int n;
const int MAXN=1e6+5;
const int b=3e5+1;
int a[MAXN];
int cnt1[MAXN],cnt2[MAXN];
int read(){
	int x=0;
	char num=getchar();
	while(num<'0'||num>'9'){
		num=getchar();
	}
	while(num>='0'&&num<='9'){
		x=x*10+num-'0';
		num=getchar();
	}
	return x;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		//scanf("%d",&a[i]);
		a[i]=read();
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		int l=i,r=i;
		int now=1;
		//printf("jin\n");
		ll maxl=min(3.3e5*3e5/n/pow(max(n/2-a[i],1),0.7),1e9);
		int pr=b,nx=b;
		cnt1[b]=cnt2[b]=1;
		while((l>1||r<n)&&abs(pr-nx)<=maxl){
			if(l>1){
				l--;
			//	printf("ja");
				if(a[l]<a[i]){
					pr--;
				}else{
					pr++;
				}
				cnt1[pr]++;
				now+=cnt2[pr]+cnt2[pr-1];
			}
			if(r<n){
				r++;
			//	printf("jb");
				if(a[r]<a[i]){
					nx++;
				}else{
					nx--;
				}
				cnt2[nx]++;
				now+=cnt1[nx]+cnt1[nx+1];
			}
		}
		//printf("chu\n");
		ans+=now*1ll*a[i];
		memset(cnt1+b-(i-l),0,((i-l)*2+1)*4);
		memset(cnt2+b-(r-i),0,((r-i)*2+1)*4);
	}
	printf("%lld",ans);
}