// Slower C++ solution:
#include<bits/stdc++.h>

#define ci const int&

#define Updl(x) (t[x].vl=Mrgl(t[x<<1].vl,t[x<<1|1].vl))

#define Updr(x) (t[x].vr=Mrgr(t[x<<1].vr,t[x<<1|1].vr))

#define pi pair<int,int>

#define f first

#define s second

using namespace std;

struct node{

	int l,r;

	pi vl,vr;

}t[400010];

int n,p[100010],pos[100010],l1,l2,r1,r2;

long long ans;

pi tmp;

pi Mrgl(const pi&x,const pi&y){

	return x.f>y.f?(pi){x.f,max(x.s,y.f)}:(pi){y.f,max(x.f,y.s)};

}

pi Mrgr(const pi&x,const pi&y){

	return x.f<y.f?(pi){x.f,min(x.s,y.f)}:(pi){y.f,min(x.f,y.s)};

}

void Build(ci x,ci l,ci r){

	t[x].l=l,t[x].r=r;

	if(l==r)return(void)(t[x].vr.f=pos[l],t[x].vr.s=n+1);

	int mid=l+r>>1;

	Build(x<<1,l,mid),Build(x<<1|1,mid+1,r),Updr(x);

}

void Changel(ci x,ci id,ci v){

	if(t[x].l==t[x].r)return(void)(t[x].vl.f=v);

	int mid=t[x].l+t[x].r>>1;

	id<=mid?Changel(x<<1,id,v):Changel(x<<1|1,id,v),Updl(x);

}

void Changer(ci x,ci id){

	if(t[x].l==t[x].r)return(void)(t[x].vr.f=n+1);

	int mid=t[x].l+t[x].r>>1;

	id<=mid?Changer(x<<1,id):Changer(x<<1|1,id),Updr(x);

}

pi Queryl(ci x,ci l,ci r){

	if(l>r)return(pi){0,0};

	if(t[x].l==l&&t[x].r==r)return t[x].vl;

	int mid=t[x].l+t[x].r>>1;

	return r<=mid?Queryl(x<<1,l,r):(l>mid?Queryl(x<<1|1,l,r):(Mrgl(Queryl(x<<1,l,mid),Queryl(x<<1|1,mid+1,r))));

}

pi Queryr(ci x,ci l,ci r){

	if(l>r)return(pi){n+1,n+1};

	if(t[x].l==l&&t[x].r==r)return t[x].vr;

	int mid=t[x].l+t[x].r>>1;

	return r<=mid?Queryr(x<<1,l,r):(l>mid?Queryr(x<<1|1,l,r):(Mrgr(Queryr(x<<1,l,mid),Queryr(x<<1|1,mid+1,r))));

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;++i)scanf("%d",&p[i]),pos[p[i]]=i;

	Build(1,1,n);

	for(int i=1;i<=n;++i){

		Changer(1,p[i]),Changel(1,p[i],i),tmp=Queryl(1,p[i]+1,n),l1=tmp.f,l2=tmp.s,tmp=Queryr(1,p[i]+1,n),r1=tmp.f,r2=tmp.s;

		ans+=1ll*(i-l1)*(r2-r1)*p[i]+1ll*(l1-l2)*(r1-i)*p[i];

	}

	printf("%lld",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 10.761723275163442x):
//#pragma GCC target("avx2")

//#pragma GCC optimize("O3")

   

//#include <x86intrin.h>

#include <bits/stdc++.h>   

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

 

using namespace __gnu_pbds;

using namespace std;



template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

     

#define F first

#define S second           

#define lb lower_bound               

#define ub upper_bound

#define pb push_back

#define pf push_front    

#define ppb pop_back

#define mp make_pair                                     

#define bpp __builtin_popcountll                                                                                        

#define sqr(x) ((x) * (x)) 

#define al 0x3F3F3F3F

#define sz(x) (int)x.size()

#define all(x) x.begin(), x.end()

#define in insert

#define ppf pop_front

#define endl '\n'

//#define int long long

 

typedef unsigned long long ull;

typedef long long ll;

typedef long double ld;

typedef pair <int, int> pii;

 

const int mod = (int)1e9 + 7;

const int N = (int)3e5 + 123;

const ll inf = (ll)1e18 + 1;



const double pi = acos (-1.0);

const double eps = 1e-7;                  

const int dx[] = {0, 0, 1, 0, -1};

const int dy[] = {0, 1, 0, -1, 0};



int n, a[N], l[N], r[N], mx[20][N], lg[N];

ll ans;

stack <int> st;



inline int get (int l, int r) {

   int len = lg[r - l + 1];

   return max (mx[len][l], mx[len][r - (1 << len) + 1]);

}



inline void boost () {                    

   ios_base :: sync_with_stdio (NULL);

   cin.tie (NULL), cout.tie (NULL);          

}                                                     



inline void Solve () {

   cin >> n;

   lg[0] = -1;

   for (int i = 1; i <= n; i ++) cin >> a[i], mx[0][i] = a[i], lg[i] = lg[i / 2] + 1;   

   for (int p = 1; (1 << p) <= n; p ++)

      for (int i = 1; i + (1 << p) - 1 <= n; i ++)

         mx[p][i] = max (mx[p - 1][i], mx[p - 1][i + (1 << (p - 1))]);

   for (int i = 1; i <= n; i ++) {

      while (sz (st) && a[st.top ()] < a[i]) st.pop ();

      if (!sz (st)) l[i] = 0;

      else l[i] = st.top ();

      st.push (i);

   }

   st = stack <int> ();

   for (int i = n; i >= 1; i --) {

      while (sz (st) && a[st.top ()] < a[i]) st.pop ();

      if (!sz (st)) r[i] = n + 1;

      else r[i] = st.top ();

      st.push (i);

   }

   for (int i = 1; i <= n; i ++) {

      if (l[i] == 0 && r[i] == n + 1) continue;

      if (r[i] != n + 1) {

         int pos = n + 1;

         int L = r[i] + 1, R = n;

         while (L <= R) {

            int mid = L + R >> 1;

            if (get (r[i] + 1, mid) > a[i]) pos = mid, R = mid - 1;

            else L = mid + 1;

         }

         ans += 1ll * (i - l[i]) * (pos - r[i]) * a[i];

      }     

      if (l[i]) {

         int pos = 0;

         int L = 1, R = l[i] - 1;

         while (L <= R) {

            int mid = L + R >> 1;

            if (get (mid, l[i] - 1) > a[i]) pos = mid, L = mid + 1;

            else R = mid - 1; 

         }

         ans += 1ll * (l[i] - pos) * (r[i] - i) * a[i];

      }

   }

   cout << ans;

}



main () {                                       

// freopen (".in", "r", stdin);    

// freopen (".out", "w", stdout);              

   boost ();

   int tt = 1;

   //cin >> tt;   

   while (tt --) {

      Solve ();

   }                                               

   return 0;      

}