#include<bits/stdc++.h>
#define lowbit(i) ((i)&(-i))
#define INF 0x3f3f3f3f
using namespace std;
const int N=300005;
int a[N],b[N],n,mx,pos[N],h[N+N];
long long ans;
void solve(int l,int r,int x){
	for(int i=l;i<=r;++i)b[i]=(a[i]<a[x])?-1:1;
	int s=0,as=0;
	for(int i=x;i>=l;--i)s+=b[i],h[s+n]++;
	s=0;
	for(int i=x+1;i<=r;++i)as+=h[n+2-s]+h[n+1-s],s+=b[i];
	as+=h[n+2-s]+h[n+1-s];
	s=0;
	for(int i=x;i>=l;--i)s+=b[i],h[s+n]--;
	ans+=1ll*as*a[x];
	// cerr<<a[x]<<" "<<as<<"\n";
}
int f(int x){
	if(x<=500)return n;
	if(x<=5000)return n/10;
	else return 500;
}
signed main(){
	cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i],pos[a[i]]=i;
	for(int i=1;i<=n;++i){
		int y=f(abs(i-n/2));
		solve(max(1,pos[i]-y),min(n,pos[i]+y),pos[i]);
	}cout<<ans;
	return 0;
}
//4 1 4 2 3