#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n,p[300010],P[300010];
int F[600010],*f=F+300005;
int G[600010],*g=G+300005;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i];
		P[p[i]]=i;
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		int lim=1.5e4*n/3e5/pow(max(1,abs(p[i]-(n>>1))),0.4);
		int j=i,k=i,s1=0,s2=0,sum=1;
		f[0]=g[0]=1;
		while((j>1||k<n)&&abs(s1)<lim&&abs(s2)<lim)
		{
			if(j>1)
			{
				j--;
				f[s1+=p[j]<p[i]?-1:1]++;
				sum+=g[s1]+g[s1-1];
			}
			if(k<n)
			{
				k++;
				g[s2+=p[k]<p[i]?1:-1]++;
				sum+=f[s2]+f[s2+1];
			}
		}
		ans+=(long long)p[i]*sum;
		memset(f-(i-j),0,(i-j<<1)+1<<2);
		memset(g-(k-i),0,(k-i<<1)+1<<2);
	}
	cout<<ans<<endl;
	return 0;
}