#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
#define ep emplace_back
template <typename T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
const int N=3e5+5;
int n;
int a[N], pos[N];
int mx[N<<2], mn[N<<2], tag[N<<2];
inline void build(int p, int l, int r){
	if(l==r){
		mx[p]=mn[p]=-l;
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1, l, mid); build(p<<1|1, mid+1, r);
	mx[p]=max(mx[p<<1], mx[p<<1|1]);
	mn[p]=min(mn[p<<1], mn[p<<1|1]);
}
inline void down(int p){
	if(tag[p]){
		tag[p<<1]+=tag[p]; tag[p<<1|1]+=tag[p];
		mx[p<<1]+=tag[p]; mx[p<<1|1]+=tag[p];
		mn[p<<1]+=tag[p]; mn[p<<1|1]+=tag[p];
		tag[p]=0;
	}
}
inline void mdf(int p, int l, int r, int L, int R, int v){
	if(L<=l&&r<=R){
		mx[p]+=v; mn[p]+=v; tag[p]+=v;
		return ;
	}
	int mid=(l+r)>>1;
	down(p);
	if(L<=mid) mdf(p<<1, l, mid, L, R, v);
	if(R>mid) mdf(p<<1|1, mid+1, r, L, R, v);
	mx[p]=max(mx[p<<1], mx[p<<1|1]);
	mn[p]=min(mn[p<<1], mn[p<<1|1]);
}
int cnt[N*2];
inline void fil(int p, int l, int r, int L, int R, int v){
	if(L<=l&&r<=R){
		if(l==r){
			cnt[mx[p]+N]+=v;
			return ;
		}
		int mid=(l+r)>>1;
		down(p);
		fil(p<<1, l, mid, L, R, v); fil(p<<1|1, mid+1, r, L, R, v);
		return ;
	}
	int mid=(l+r)>>1;
	down(p);
	if(L<=mid) fil(p<<1, l, mid, L, R, v);
	if(R>mid) fil(p<<1|1, mid+1, r, L, R, v);
}
inline ll get(int p, int l, int r, int L, int R){
	if(L<=l&&r<=R){
		if(l==r){
			return cnt[mx[p]+N]+cnt[mx[p]+1+N];
		}
		int mid=(l+r)>>1;
		down(p);
		return get(p<<1, l, mid, L, R)+get(p<<1|1, mid+1, r, L, R);
	}
	int mid=(l+r)>>1;
	down(p);
	ll ret=0;
	if(L<=mid) ret+=get(p<<1, l, mid, L, R);
	if(R>mid) ret+=get(p<<1|1, mid+1, r, L, R);
	return ret;
}
inline ll gett(int p, int l, int r, int L, int R){
	if(L<=l&&r<=R){
		if(l==r){
			return cnt[mx[p]+N]+cnt[mx[p]-1+N];
		}
		int mid=(l+r)>>1;
		down(p);
		return gett(p<<1, l, mid, L, R)+gett(p<<1|1, mid+1, r, L, R);
	}
	int mid=(l+r)>>1;
	down(p);
	ll ret=0;
	if(L<=mid) ret+=gett(p<<1, l, mid, L, R);
	if(R>mid) ret+=gett(p<<1|1, mid+1, r, L, R);
	return ret;
}
inline int getv(int p, int l, int r, int x){
	if(l==r) return mx[p];
	int mid=(l+r)>>1;
	down(p);
	if(x<=mid) return getv(p<<1, l, mid, x);
	return getv(p<<1|1, mid+1, r, x);
}
inline int getr(int p, int l, int r, int L, int R, int lv, int rv){
	if(mn[p]>rv||mx[p]<lv) return -1;
	if(L<=l&&r<=R){
		if(l==r) return l;
		int mid=(l+r)>>1;
		down(p);
		int ret=-1;
		ret=getr(p<<1|1, mid+1, r, L, R, lv, rv);
		if(ret!=-1) ret=getr(p<<1, l, mid, L, R, lv, rv);
		return ret;
	}
	int mid=(l+r)>>1;
	down(p);
	int ret=-1;
	if(R>mid) ret=getr(p<<1|1, mid+1, r, L, R, lv, rv);
	if(ret!=-1&&L<=mid) ret=getr(p<<1, l, mid, L, R, lv, rv);
	return ret;
}
inline int getl(int p, int l, int r, int L, int R, int lv, int rv){
	if(mn[p]>rv||mx[p]<lv) return -1;
	if(L<=l&&r<=R){
		if(l==r) return l;
		int mid=(l+r)>>1;
		down(p);
		int ret=-1;
		ret=getl(p<<1, l, mid, L, R, lv, rv);
		if(ret!=-1) ret=getl(p<<1|1, mid+1, r, L, R, lv, rv);
		return ret;
	}
	int mid=(l+r)>>1;
	down(p);
	int ret=-1;
	if(L<=mid) ret=getl(p<<1, l, mid, L, R, lv, rv);
	if(ret!=-1&&R>mid) ret=getl(p<<1|1, mid+1, r, L, R, lv, rv);
	return ret;
}
int main(){
	// freopen("D:\\nya\\acm\\C\\test.in","r",stdin);
	// freopen("D:\\nya\\acm\\C\\test.out","w",stdout);
	read(n);
	for(int i=1; i<=n; ++i) read(a[i]), pos[a[i]]=i;
	build(1, 0, n);
	ll ans=0;
	for(int i=n; i>=1; --i){
		if(abs(i-n/2)<=300){
			if(pos[i-1]<n/2){
				fil(1, 0, n, 0, pos[i]-1, 1);
				ans+=get(1, 0, n, pos[i], n)*i;
				// cout<<"a "<<i<<' '<<get(1, 0, n, pos[i], n)<<endl;
				fil(1, 0, n, 0, pos[i]-1, -1);
			}
			else{
				fil(1, 0, n, pos[i], n, 1);
				ans+=gett(1, 0, n, 0, pos[i]-1)*i;
				// cout<<"b "<<i<<' '<<gett(1, 0, n, 0, pos[i]-1)<<endl;
				fil(1, 0, n, pos[i], n, -1);
			}
			mdf(1, 0, n, pos[i], n, 2);
			continue;
		}
		int lp=pos[i]-1, rp=pos[i], timer=0;
		while(timer<1000&&lp>=0&&rp<=n){
			++timer;
			if(timer&1){
				int vlp=getv(1, 0, n, lp);
				int nrp=getr(1, 0, n, rp+1, n, vlp, vlp+1);
				if(nrp!=-1) rp=nrp;
			}
			else{
				int vrp=getv(1, 0, n, rp);
				int nlp=getl(1, 0, 0, lp-1, n, vrp-1, vrp);
				if(nlp!=-1) lp=nlp;
			}
			if(lp!=0) --lp;
			if(rp!=n) ++rp;
		}
		// cout<<i<<' '<<lp<<' '<<rp<<endl;
		if(pos[i]*2<lp+rp){
			fil(1, 0, n, lp, pos[i]-1, 1);
			ans+=get(1, 0, n, pos[i], rp)*i;
			fil(1, 0, n, lp, pos[i]-1, -1);
		}
		else{
			fil(1, 0, n, pos[i], rp, 1);
			ans+=gett(1, 0, n, lp, pos[i]-1)*i;
			fil(1, 0, n, pos[i], rp, -1);
		}
		mdf(1, 0, n, pos[i], n, 2);
	}
	printf("%lld\n", ans);
	return 0;
}