#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 700000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int n,lg[N+1],p[N+1],ps[N+1],s[N+1],cnt[N+1];
long long ans;
bool cmp(int x,int y)
{
	return p[x]<p[y];
}
struct seg
{
	struct node
	{
		int l,r,minn,maxn,lazy;
	};
	node tree[(N<<2)+1];
	void push_up(int k)
	{
		tree[k].minn=min(tree[k<<1].minn,tree[k<<1|1].minn),tree[k].maxn=max(tree[k<<1].maxn,tree[k<<1|1].maxn);
		return;	
	}
	void spread(int k)
	{
		if (tree[k].lazy)
		{
			tree[k<<1].minn+=tree[k].lazy,tree[k<<1].maxn+=tree[k].lazy;
			tree[k<<1|1].minn+=tree[k].lazy,tree[k<<1|1].maxn+=tree[k].lazy;
			tree[k].lazy=0;
		}
		return;	
	}
	void build(int k,int l,int r)
	{
		tree[k].l=l,tree[k].r=r;
		if (l==r)
		{
			tree[k].minn=tree[k].maxn=l;
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
		return;	
	}
	void add(int k,int l,int r,int d)
	{
		if (tree[k].l==l&&tree[k].r==r)
		{
			tree[k].minn+=d,tree[k].maxn+=d,tree[k].lazy+=d;
			return;
		}
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) add(k<<1,l,r,d);
		else if (l>=mid+1) add(k<<1|1,l,r,d);
		else add(k<<1,l,mid,d),add(k<<1|1,mid+1,r,d);
		push_up(k);
		return;	
	}
	int get_minn(int k,int l,int r)
	{
		if (tree[k].l==l&&tree[k].r==r) return tree[k].minn;
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) return get_minn(k<<1,l,r);
		else if (l>=mid+1) return get_minn(k<<1|1,l,r);
		else return min(get_minn(k<<1,l,mid),get_minn(k<<1|1,mid+1,r));
	}
	int get_maxn(int k,int l,int r)
	{
		if (tree[k].l==l&&tree[k].r==r) return tree[k].maxn;
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) return get_maxn(k<<1,l,r);
		else if (l>=mid+1) return get_maxn(k<<1|1,l,r);
		else return max(get_maxn(k<<1,l,mid),get_maxn(k<<1|1,mid+1,r));
	}
};
seg T;
int main()
{
	int x,l,r,L,R;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	n=read();
	for (int i=1;i<=n;++i) p[i]=read(),ps[i]=i;
	sort(ps+1,ps+n+1,cmp),T.build(1,0,n);
	for (int i=1;i<=n;++i)
	{
		x=ps[i],T.add(1,x,n,-2),L=T.get_minn(1,x,n),R=T.get_maxn(1,x,n)+1,l=x;
		for (int j=lg[x];j>=0;--j)
			if (l-(1<<j)>=1&&max(L,T.get_minn(1,0,l-(1<<j)-1))<=min(R,T.get_maxn(1,0,l-(1<<j)-1)))
				l-=(1<<j);
		L=T.get_minn(1,0,x-1)-1,R=T.get_maxn(1,0,x-1),r=x;
		for (int j=lg[n-x+1];j>=0;--j)
			if (r+(1<<j)<=n&&max(L,T.get_minn(1,r+(1<<j),n))<=min(R,T.get_maxn(1,r+(1<<j),n)))
				r+=(1<<j);
		s[l-1]=0;
		for (int j=l;j<=r;++j)
		{
			if (p[j]>i) s[j]=s[j-1]+1;
			else s[j]=s[j-1]-1;
		}
		for (int j=l;j<=x;++j) cnt[s[j-1]+n]++;
		for (int j=x;j<=r;++j) ans+=1ll*(cnt[s[j]+n]+cnt[s[j]+1+n])*i;
		for (int j=l;j<=x;++j) cnt[s[j-1]+n]--;
	}
	printf("%lld\n",ans);
	return 0;
}