#include<iostream>
#include<cstring>
using namespace std;
const int C=3000;
int n,p[300010],P[300010];
int box[600010],*f=box+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;
	int l=max(1,n-C>>1),r=min(n,n+C>>1);
	for(int i=l;i<=r;i++)
	{
		memset(box,0,sizeof(box)),f[0]=1;
		for(int j=P[i]-1,s=0;j;j--)
		{
			f[s+=p[j]<i?-1:1]++;
		}
		int sum=f[0]+f[1];
		for(int j=P[i]+1,s=0;j<=n;j++)
		{
			s+=p[j]<i?1:-1;
			sum+=f[s]+f[s+1];
		}
		ans+=(long long)i*sum;
	}
	for(int i=1;i<=n;i++)
	{
		if(p[i]>=l&&p[i]<=r)
		{
			continue;
		}
		memset(f-(C>>1)-5,0,C+10<<2),f[0]=1;
		for(int j=i-1,s=0;j>=max(1,i-(C>>1));j--)
		{
			f[s+=p[j]<p[i]?-1:1]++;
		}
		int sum=f[0]+f[1];
		for(int j=i+1,s=0;j<=min(n,i+(C>>1));j++)
		{
			s+=p[j]<p[i]?1:-1;
			sum+=f[s]+f[s+1];
		}
		ans+=(long long)p[i]*sum;
	}
	cout<<ans<<endl;
	return 0;
}