#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#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 main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		int l=i,r=i;
		ll now=1;
		//printf("jin\n");
		ll maxl=min(((n/2!=a[i])?(n*1ll*n/abs(n/2-a[i])/abs(n/2-a[i])*8+2):n),(ll)n);
		int pr=0,nx=0;
		cnt1[b]=cnt2[b]=1;
		while((l>1||r<n)&&abs(r-l)<=maxl){
			if(l>1){
				l--;
			//	printf("ja");
				if(a[l]<a[i]){
					pr--;
				}else{
					pr++;
				}
				cnt1[pr+b]++;
				now+=cnt2[pr+b]+cnt2[pr-1+b];
			}
			if(r<n){
				r++;
			//	printf("jb");
				if(a[r]<a[i]){
					nx++;
				}else{
					nx--;
				}
				cnt2[nx+b]++;
				now+=cnt1[nx+b]+cnt1[nx+b+1];
			}
		}
		//printf("chu\n");
		ans+=now*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);
}