#include <bits/stdc++.h>
#define lli long long int
#define pb push_back
#define mod 1000000007
#pragma GCC optimize ("-O2")
#define mod2 998244353
#define MAXN 1000000000
#define v32 vector<int>
#define v64 vector<lli>
#define v1024 vector <vector <int>>
#define v4096 vector <vector <lli>>
#define vt vector
#define f(x, y, z) for (lli x = y; x < z; x++)
#define fd(x, y, z) for (lli x = y; x > z; x--)
#define lb lower_bound
#define ld long double
#define m64 map<lli,lli>
#define m32 map<int,int>
#define m64it map<lli,lli>::iterator
#define m32it map<int,int>::iterator
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ist insert
#define endl "\n"
#include <ext/pb_ds/assoc_container.hpp>
#define p_q priority_queue 
#define min_p_q priority_queue <int,vt <int>,greater <int>>
using namespace std;
using namespace __gnu_pbds; 
int op(int a, int b){
  return max(a,b);
};

inline int log2Up(int n) {
	int res = 0;
	while ((1 << res) < n) {
		res++;
	}
	return res;
}

class SqrtTree {
	private:
		int n, lg;
		vector<int> v;
		vector<int> clz;
		vector<int> layers;
		vector<int> onLayer;
		vector< vector<int> > pref;
		vector< vector<int> > suf;
		vector< vector<int> > between;
		
		void build(int layer, int lBound, int rBound) {
			if (layer >= (int)layers.size()) {
				return;
			}
			int bSzLog = (layers[layer]+1) >> 1;
			int bCntLog = layers[layer] >> 1;
			int bSz = 1 << bSzLog;
			int bCnt = 0;
			for (int l = lBound; l < rBound; l += bSz) {
				bCnt++;
				int r = min(l + bSz, rBound);
				pref[layer][l] = v[l];
				for (int i = l+1; i < r; i++) {
					pref[layer][i] = op(pref[layer][i-1], v[i]);
				}
				suf[layer][r-1] = v[r-1];
				for (int i = r-2; i >= l; i--) {
					suf[layer][i] = op(v[i], suf[layer][i+1]);
				}
				build(layer+1, l, r);
			}
			for (int i = 0; i < bCnt; i++) {
				int ans = 0;
				for (int j = i; j < bCnt; j++) {
					int add = suf[layer][lBound + (j << bSzLog)];
					ans = (i == j) ? add : op(ans, add);
					between[layer][lBound + (i << bCntLog) + j] = ans;
				}
			}
		}
	public:
		inline int query(int l, int r) {
			if (l == r) {
				return v[l];
			}
			if (l + 1 == r) {
				return op(v[l], v[r]);
			}
			int layer = onLayer[clz[l ^ r]];
			int bSzLog = (layers[layer]+1) >> 1;
			int bCntLog = layers[layer] >> 1;
			int lBound = (l >> layers[layer]) << layers[layer];
			int lBlock = ((l - lBound) >> bSzLog) + 1;
			int rBlock = ((r - lBound) >> bSzLog) - 1;
			int ans = suf[layer][l];
			if (lBlock <= rBlock) {
				ans = op(ans, between[layer][lBound + (lBlock << bCntLog) + rBlock]);
			}
			ans = op(ans, pref[layer][r]);
			return ans;
		}
		
		SqrtTree( vector<int>& v)
			: n((int)v.size()), lg(log2Up(n)), v(v), clz(1 << lg), onLayer(lg+1) {
			clz[0] = 0;
			for (int i = 1; i < (int)clz.size(); i++) {
				clz[i] = clz[i >> 1] + 1;
			}
			int tlg = lg;
			while (tlg > 1) {
				onLayer[tlg] = (int)layers.size();
				layers.push_back(tlg);
				tlg = (tlg+1) >> 1;
			}
			for (int i = lg-1; i >= 0; i--) {
				onLayer[i] = max(onLayer[i], onLayer[i+1]);
			}
			pref.assign(layers.size(), vector<int>(n));
			suf.assign(layers.size(), vector<int>(n));
			between.assign(layers.size(), vector<int>(1 << lg));
			build(0, 0, n);
		}
};

void DEBUG_ARR(v32 a)
{
	f(i,0,a.size())cout<<a[i]<<" ";
	cout<<"\n";
}
 
int main() 
{ 
  fastio;
  int n;cin>>n;
  v32 p(n);f(i,0,n)cin>>p[i];
  SqrtTree P(p);
  v32 l(n,0),r(n),l2(n),r2(n);
  f(i,0,n){
    int it=i,jt=n-1;
    while(it!=jt){
      int mid=(it+jt)/2;
      if(P.query(i,mid)==p[i])it=mid+1;
      else jt=mid;
    }
	if(it!=n-1)
    it--;
	else if(P.query(i,it)!=p[i])it--;
    r[i]=it;
    if(it==n-1){
      r2[i]=-1;
      continue;
    }
	it+=2,jt=n-1;
	if(it==n){
		r2[i]=n-1;
		continue;
	}
	else if(it>n){r2[i]=-1;continue;}
    while (it!=jt)
    {
      int mid=(it+jt)/2;
      if(P.query(r[i]+2,mid)<p[i])it=mid+1;
      else jt=mid;
    }
    if(it!=n-1)it--;
	else {
		if(p[i]<P.query(r[i]+2,it))it--;
	}
    r2[i]=it;
  }
  f(i,0,n){
    int it=0,jt=i;
    while(it!=jt){
      int mid=(it+jt)/2;
      if(P.query(mid,i)==p[i])jt=mid;
      else it=mid+1;
    }
    l[i]=it;
    it=0,jt=l[i]-2;
	l2[i]=l[i]-1;
    if(l2[i]<=0)continue;
    while (it!=jt)
    {
      int mid=(it+jt)/2;
      if(P.query(mid,l[i]-2)<p[i])jt=mid;
      else it=mid+1;
    }
	if(P.query(it,l[i]-2)>p[i])it++;
    l2[i]=it;
  } 
  //DEBUG_ARR(l);
  //DEBUG_ARR(l2);
  //DEBUG_ARR(r);
  //DEBUG_ARR(r2);
  lli ans=0;
  f(i,0,n){
	  if(l2[i]!=-1 && r2[i]!=-1 ){
         ans+=p[i]*((i-l[i]+1)*(r2[i]-r[i])+(r[i]-i+1)*(l[i]-l2[i])); 
	  }
	  else if(l2[i]==-1 && r2[i]!=-1){
         ans+=p[i]*((i-l[i]+1)*(r2[i]-r[i]));
	  }
	  else if(l2[i]!=-1 && r2[i]==-1){
         ans+=p[i]*((r[i]-i+1)*(l[i]-l2[i]));
	  }
  }
  cout<<ans<<"\n";
  return 0; 	
}

Measured memory_bytes: 9972