#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <random>

using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
class Monoid {
public:
    using t = tuple<int,int,int,int>;
    static t id() {
        return make_tuple(1000000,1000000,-1,-1);
    }
    static t op(const t& l, const t& r) {
		int m1,m2;
		if(get<0>(l) < get<0>(r)){
			m1 = get<0>(l);
			m2 = min(get<1>(l),get<0>(r));
		}
		else{
			m1 = get<0>(r);
			m2 = min(get<1>(r),get<0>(l));
		}
		int M1,M2;
		if(get<2>(l) > get<2>(r)){
			M1 = get<2>(l);
			M2 = max(get<3>(l),get<2>(r));
		}
		else{
			M1 = get<2>(r);
			M2 = max(get<3>(r),get<2>(l));
		}
        return make_tuple(m1,m2,M1,M2);
    }
};
template< typename M >
class SegmentTree {
	using T = typename M::t;
	const int n;
	vector<T> data;
	int size(int n_) {
        int res = 1;
        while (res <= n_) {
			res <<= 1;
		}
        return res;
    }
	public:
    SegmentTree(int n_)
        : n(size(n_)), data(n * 2, M::id()) {}
    SegmentTree(int n_, T v)
        : n(size(n_)), data(n * 2, v) {}
    SegmentTree(const vector<T>& data_)
        : n(size(data_.size())), data(n * 2, M::id()) {
            init(data_);
    }
    void init() {
        for (int i = n - 1; i >= 1; i--) data[i] = M::op(data[i * 2], data[i * 2 + 1]);
    }
    void init(const vector<T>& data_) {
        for (int i = 0; i < (int)data_.size(); i++) data[i + n] = data_[i];
        init();
    }
  	void Update(int k,const T x){
    	k += n;
    	data[k] = x;
    	while(k >>= 1){
      		data[k] = M::op(data[2*k+0],data[2*k+1]);
    	}
  	}
	//[a,b)
  	T Query(int a,int b){
    	T L = M::id(), R = M::id();
    	for(a += n,b += n;a < b;a >>= 1,b >>= 1){
      		if(a & 1) L = M::op(L,data[a++]);
      		if(b & 1) R = M::op(data[--b],R);
    	}
    	return M::op(L,R);
  	}
	T Query(int a){
    	return data[a+n];
  	}
	//[0,bc]がFを満たす最小のbc(>=0)ないなら-1
	int MinSearch(function<bool(T)> F){
		if(!F(data[1])){
			return -1;
		}
    	T L = M::id();
		int a = 1;
		while(a < n){
			if(!F(M::op(L,data[a << 1]))){
				L = M::op(L,data[a << 1]);
				a = (a << 1) + 1;
			}
			else{
				a <<= 1;
			}
		}
    	return a-n;
  	}
	//[v,bc]がFを満たす最小のbc(>=v)ないなら-1
	int MinSearch(int v,function<bool(T)> F){
		int a = v+n;
		T L = data[a];
		if(F(L)){
			return v;
		}
		while(a > 1){
			if((a & 1) == 0){
				if(F(M::op(L,data[a+1]))){
					a++;
					break;
				}
				L = M::op(L,data[a+1]);
			}
			a >>= 1;
		}
		if(a == 1){
			return -1;
		}
		while(a < n){
			if(!F(M::op(L,data[a << 1]))){
				L = M::op(L,data[a << 1]);
				a = (a << 1) + 1;
			}
			else{
				a <<= 1;
			}
		}
    	return a-n;
  	}
};
int P[100000];
int Place[1000001];
void Calc(){
	int N = rei();
	for(int i=0;i<N;i++){
		int x = rei();
		Place[x] = i;
		P[i] = x;
	}
	SegmentTree<Monoid> Seg(N);
	long ans = 0;
	for(int i=N;i>0;i--){
		tuple<int,int,int,int> LS = Seg.Query(0,Place[i]+1);
		tuple<int,int,int,int> RS = Seg.Query(Place[i],N);
		int L2 = max(get<3>(LS),-1);
		int L1 = max(get<2>(LS),-1);
		int R2 = min(get<1>(RS),N);
		int R1 = min(get<0>(RS),N);
		int X = Place[i];
		Seg.Update(Place[i],make_tuple(Place[i],1000000,Place[i],-1));
		long c = 1LL*(X-L2)*(R1-X) + 1LL*(X-L1)*(R2-X) - 2LL*(X-L1)*(R1-X);
 		ans += c*i;
	}
	cout << ans << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 7040