#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll; 
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=3e5+3;
int n,a[N],b[N];
const int M=1<<20;
int mx[M],mi[M],tg[M];
#define mid ((l+r)>>1)
#define ls x<<1
#define rs x<<1|1
inline void ad(int x,int k){ mx[x]+=k,mi[x]+=k,tg[x]+=k; }
inline void pd(int x){ ad(ls,tg[x]),ad(rs,tg[x]),tg[x]=0; }
inline void pu(int x){ mx[x]=max(mx[ls],mx[rs]); mi[x]=min(mi[ls],mi[rs]); }
inline void ad(int x,int l,int r,int nx,int k){
	if(nx<=l)return ad(x,k); 
	pd(x);
	if(nx<=mid)ad(ls,l,mid,nx,k);
	ad(rs,mid+1,r,nx,k);
	pu(x);
}
inline pii qr(int x,int l,int r,int nl,int nr){
	if(nl<=l&&r<=nr)return P(mi[x],mx[x]);
	pd(x);
	int a=INT_MAX,b=INT_MIN;
	if(nl<=mid){
		pii res=qr(ls,l,mid,nl,nr);
		a=min(a,res.fi),b=max(b,res.se);
	}
	if(mid<nr){
		pii res=qr(rs,mid+1,r,nl,nr);
		a=min(a,res.fi),b=max(b,res.se);
	}
	return P(a,b);
}
inline int find1(int x,int l,int r,int nx,pii K){
	if(l>nx||mx[x]<K.fi||mi[x]>K.se)return -1;
	if(l==r)return l;
	pd(x);
	int res=find1(ls,l,mid,nx,K);if(~res)return res;
	return find1(rs,mid+1,r,nx,K);
}
inline int find2(int x,int l,int r,int nx,pii K){
	if(r<nx||mx[x]<K.fi||mi[x]>K.se)return -1;
	if(l==r)return l;
	pd(x);
	int res=find2(rs,mid+1,r,nx,K);if(~res)return res;
	return find2(ls,l,mid,nx,K);
}
int main() {
    //freopen("data.in", "r", stdin);
    // freopen("myans.out","w",stdout);
	n=read();
	rep(i,1,n)a[i]=read(),b[a[i]]=i;
	ll ans=0;
	rep(i,1,n)ad(1,0,n,i,-1);
	rep(i,1,n){
		int x=b[i];
		ad(1,0,n,x,2);
		pii res=qr(1,0,n,x,n);--res.fi;
		int lp=find1(1,0,n,x-1,res);
		res=qr(1,0,n,0,x-1);++res.se;
		int rp=find2(1,0,n,x,res);
		static int t[N<<1];
		int s=0;
		rep(j,lp+1,x)++t[s+N],s+=(a[j]<=i?1:-1);
		ll cnt=0;
		rep(j,x,rp)cnt += t[s+N]+t[s+N-1],s+=(a[j+1]<=i?1:-1);
		ans += cnt*i;
		s=0; rep(i,lp+1,x)t[s+N]=0,s+=(a[i]<=x?1:-1);
		//printf("%d %d %lld %d\n",lp,rp,cnt,x);
	}
	cout<<ans;
    return 0;
}