//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <algorithm>
#include <numeric>
#include <random>
#include <stdio.h>

using namespace std;

typedef long long LL;
typedef long double LD;
typedef string ST;


#define REP(i,n) for(LL (i)=0;(i)<(n);(i)++)
#define ALL(v) v.begin(), v.end()
#define PRINTLN(v) for(auto (a): v )   cerr << a << endl
#define PRINTSP(v) for(auto (a): v ) {cerr << a << " ";} cerr << endl

vector<LL> arg_sort(vector<LL> A, bool ascend = true) {

  // 配列のインデックス indiecs = {0, 1, 2, 3, 4} を作成する。
  vector<LL> index(A.size());
  iota(index.begin(), index.end(), 0);

  // ソートする。
  if (ascend) {
    std::sort(index.begin(), index.end(), [&A](LL i1, LL i2) {
      return A[i1] < A[i2];
      });
  }
  else {
    std::sort(index.begin(), index.end(), [&A](LL i1, LL i2) {
      return A[i1] > A[i2];
      });
  }

  return index;
}

void func() {
  LL N;
  cin >> N;
  vector<LL> P(N);
  REP(i, N) {
    cin >> P[i];
  }

  auto index = arg_sort(P,false);

  //PRINTSP(index);
  //PRINTSP(P);

  set<LL> S;
  LL C = 0;
  REP(i, N) {
    auto j = index[i];

    S.insert(j);
    LL left1, left2 ;
    {
      auto it = S.find(j);
      if (it != S.begin()) {
        it--;
        left1 = *it;

        if (it != S.begin()) {
          it--;
          left2 = *it;
        }
        else {
          left2 = -1;
        }
      }
      else {
        left1 = -1;
        left2 = -1;
      }

    }
    LL right1,right2;
    {
      auto it = S.find(j);
      if ((++it) != S.end()) {
        right1 = *it;
        if ((++it) != S.end()) {
          right2 = *it;
        }
        else {
          right2 = N;
        }
      }
      else {
        right1 = N;
        right2 = N;
      }
    }

    LL lc1 = j - left1;
    LL lc2 = j - left2;
    LL rc1 = right1 - j;
    LL rc2 = right2 - j;

    

    
    //fprintf(stderr, "%2lld, %2lld, %2lld\n", c,j-left1,right1-j);
    //fprintf(stderr, "%2lld, j=%2lld, l2=%2lld, l1=%2lld, r1=%2lld, r2=%2lld\n", P[j], j, left2, left1, right1, right2);
    //fprintf(stderr, "%2lld, j=%2lld, lc2=%2lld, lc1=%2lld, rc1=%2lld, rc2=%2lld\n", P[j], j, lc2, lc1, rc1, rc2);
    LL c =  ((lc2 - lc1) * rc1 + (lc1 * (rc2 - rc1)));
    //fprintf(stderr, "%2lld, j=%2lld, %2lld, %2lld, %2lld, %2lld, c=%lld\n", P[j], j, lc2 - lc1, rc1, lc1, rc2-rc1,c);
    // 集合Cの中でjより小さいもので最大
    C += P[j] * c;

  }


  cout << C;
}

void first_sum() {
  LL N;
  cin >> N;
  vector<LL> P(N);
  REP(i, N) {
    cin >> P[i];
  }

  auto index = arg_sort(P, false);

  PRINTSP(index);
  PRINTSP(P);

  LL C = 0;
  set<LL> S;
  REP(i, N) {
    auto j = index[i];

    S.insert(j);
    LL left;
    {


      auto it = S.find(j);
      if (it != S.begin()) {
        it--;
        left = *it;
      }
      else {
        left = -1;
      }
    }
    LL right;
    {
      auto it = S.find(j);
      it++;
      if (it != S.end()) {
        right = *it;
      }
      else {
        right = N;
      }
    }

    LL c = P[j]*(j - left) * (right - j);
    C += c;
    fprintf(stderr, "%2lld, %2lld, %2lld\n", c, j - left, right - j);
    fprintf(stderr, "%2lld, j=%2lld, l=%2lld, r=%2lld\n", P[j], j, left, right);
    // 集合Cの中でjより小さいもので最大


  }


  //cerr << S.size();
}







#ifdef CALC_TIME 
#include <windows.h>
int main()
{
  LARGE_INTEGER freq;
  QueryPerformanceFrequency(&freq);
  LARGE_INTEGER start, end;
  QueryPerformanceCounter(&start);
  // 何かの処理
  func();
  QueryPerformanceCounter(&end);
  double time = static_cast<double>(end.QuadPart - start.QuadPart) * 1000.0 / freq.QuadPart;
  fprintf(stderr, "\n%lf[ms]\n", time);
  return 0;
}
#else 
int main()
{
  func();
  return 0;
}
#endif





Measured memory_bytes: 6512