#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#include <stack>
using namespace std;
 
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define ktya(x) sort(all(x))
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 1e18
#define INFLL 1000000000000000007LL
#define SIZE 200105
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define PI (acos(-1))
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
ll MOD = 1000000007;
// ll MOD=998244353;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
ll powMod(ll x, ll k, ll m) {//x^k (mod n)
	if (k == 0)     return 1;
	if (k % 2 == 0) return powMod(x*x % m, k/2, m);
	else            return x*powMod(x, k-1, m) % m;
}
int N,K;
int cnt[114514]={0};
vi PP;
struct BIT
{
	int bit[SIZE];
	int n;//bit.n=N+2で初期化
	
	void add(int k,int x){//(k番目にxを足す) 1-index
		while(k<=n){
			bit[k]+=x;
			k=k+(k&-k);//一番右端
		}
	}

	int sum(int k){//kまでの和
		int ret=0;
		while(k>0){
			ret+=bit[k];
			k=k-(k&-k);//一番左端
		}
		return ret;
	}

	int sum(int a,int b){//a~bの和
		return sum(b)-sum(a-1);
	}

};

BIT bit;
int invmap[114514];
int main(){
	cin>>N;
	rep(i,N){
		int x;
		cin>>x;
		PP.pb(x);
		invmap[x]=i+1;
	}
	bit.n=N+2;
	bit.add(invmap[N],1);
	ll ans=0;
	for(int j=N-1;j>=1;j--){
		//cout<<"ima"<<j<<" ";
		bit.add(invmap[j],1);
		int pos=invmap[j];
		int now=bit.sum(pos);
		if(now>1){
			//now-1になるところを探す。
			
			int ng=0,ok=pos-1;
			while(ok-ng>1){
				int mi=(ok+ng)/2;
				if(bit.sum(mi)==now-1)ok=mi;
				else ng=mi;
			}
			int lo=0,hi=N+1;
			if(now>2){
				int temp=ng;
				while(temp-lo>1){
					int mi=(temp+lo)/2;
					if(bit.sum(mi)==now-2)temp=mi;
					else lo=mi;
				}
				lo=temp;

			}
			if(N-j+1-now>0){
				int temp=pos;
				while(hi-temp>1){
					int mi=(temp+hi)/2;
					if(bit.sum(mi)==now)temp=mi;
					else hi=mi;
				}
			}
			//cout<<lo<<" "<<ok<<" "<<pos<<" "<<hi<<endl;
			ans+=(ll)(hi-pos)*(ll)(ok-lo)*(ll)j;
		}
		if(now<N-j+1){
			//now+1になるところを探す。
			int ng=pos,ok=N+1;
			while(ok-ng>1){
				int mi=(ok+ng)/2;
				if(bit.sum(mi)==now)ng=mi;
				else ok=mi;
			}
			int lo=0,hi=N+1;
			if(now>1){
				int temp=pos-1;
				while(temp-lo>1){
					int mi=(temp+lo)/2;
					if(bit.sum(mi)==now-1)temp=mi;
					else lo=mi;
				}
				lo=temp;

			}
			if(N-j-now>0){
				int temp=ok;
				while(hi-temp>1){
					int mi=(temp+hi)/2;
					if(bit.sum(mi)==now+1)temp=mi;
					else hi=mi;
				}
			}
			//cout<<lo<<" "<<pos<<" "<<ok<<" "<<hi<<endl;
			ans+=(ll)(hi-ok)*(ll)(pos-lo)*(ll)j;
		}
	}
	cout<<ans<<endl;
}




Measured memory_bytes: 1528