#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

template <class T>
class SegTree{
    int n;
    vector<T> data;
    T def; //初期値,単位元
    function<T(T, T)> operation; //区間クエリで使う処理
    function<T(T, T)> update; //1点更新で使う処理

    //区間[a,b)の総和
    T _query(int a, int b, int k, int l, int r){
        if(r <= a || b <= l) return def; //交差しない時
        if(a <= l && r <= b) return data[k]; //[l,r)が完全に含まれるとき
        else{
            T c1 = _query(a, b, (k << 1)+1, l, (l+r)/2);
            T c2 = _query(a, b, (k << 1)+2, (l+r)/2, r);
            return operation(c1, c2);
        }
    }

  public:
    // _n:必要サイズ _def:初期値かつ単位元 _operation:クエリ関数
    // _update:更新関数
    SegTree(size_t _n, T _def, function<T(T, T)> _operation, function<T(T, T)> _update)
        : def(_def), operation(_operation), update(_update){
        n = 1;
        while(n < _n){
            n *= 2;
        }
        data = vector<T>(2*n-1, def);
    }

    //場所i(0-idx)の値をxで更新
    void change(int i, T x){
        i += n-1;
        data[i] = update(data[i], x);
        while(i > 0){
            i = (i-1)/2;
            data[i] = operation(data[(i<<1) + 1], data[(i<<1) + 2]);
        }
    }

    T query(int a, int b){
        return _query(a, b, 0, 0, n);
    }

    T operator[](int i){
        return data[i+n-1];
    }
};

int main(void){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N; cin >> N;
  vector<int> A(N); rep(i, N) cin >> A[i];
  SegTree<int> st(N, 0, 
                [](int a, int b){return max(a, b);},
                [](int a, int b){return b;});
  rep(i, N) st.change(i, A[i]);
  vector<int> Left[2], Right[2];
  rep(i, 2){Left[i].resize(N, -1), Right[i].resize(N, -1);}

  /* 愚直計算: ansの計算の正当性verify
  rep(i, N){
    int val = A[i];
    for(int r = i+1; r < N; r++){
      if(val < A[r]){
        if(Right[0][i] == -1) Right[0][i] = r;
        else if(Right[1][i] == -1) Right[1][i] = r;
      }
    }
    for(int l = i-1; l >= 0; l--){
      if(A[l] > val){
        if(Left[0][i] == -1) Left[0][i] = l;
        else if(Left[1][i] == -1) Left[1][i] = l;
      }
    }
  }
  */

  rep(i, N){
    //iより左側でA[i]より大きく最もiに近い添え字は?
    int ok = -1, ng = i;
    int m = (ok+ng)/2;
    while(abs(ok-ng) > 1){
      if(st.query(m, i) > A[i]) ok = m;
      else ng = m;
      m = (ok+ng)/2;
    }
    if(ok != -1){
      int j = ok;
      Left[0][i] = ok;
      ng = ok; ok = -1;
      m = (ok+ng)/2;
      while(abs(ok-ng) > 1){
        if(st.query(m, j) > A[i]) ok = m;
        else ng = m;
        m = (ok+ng)/2;
      }
      if(ok != -1) Left[1][i] = ok;
    }
    ok = N+1, ng = i+1;
    m = (ok+ng)/2;
    while(abs(ok-ng) > 1){
      if(A[i] < st.query(i, m)) ok = m; //厳密には(i+1, m)だけどまあヨシ
      else ng = m;
      m = (ok+ng)/2;
    }
    if(ok != N+1){
      int j = ok;
      Right[0][i] = ok-1;
      ng = ok; ok = N+1;
      m = (ok+ng)/2;
      while(abs(ok-ng) > 1){
        if(A[i] < st.query(j, m)) ok = m;
        else ng = m;
        m = (ok+ng)/2;
      }
      if(ok != N+1) Right[1][i] = ok-1;
    }
  }
  /*
  rep(i, 2){
    rep(j, N) cout << Left[i][j] << " ";
    cout << endl;
  }
  rep(i, 2){
    rep(j, N) cout << Right[i][j] << " ";
    cout << endl;
  }
  */
  ll ans = 0;
  for(ll i = 0; i < N; i++){
    ll l2 = Left[1][i], l1 = Left[0][i], r1 = Right[0][i], r2 = Right[1][i];
    if(Left[1][i] != -1 && Right[1][i] != -1){
      ans += ((l1-l2)*(r1-i) + (i-l1)*(r2-r1)) * A[i];
    }
    else if(Left[1][i] != -1 && Right[0][i] != -1){
      ans += ((l1-l2)*(r1-i) + (i-l1)*(N-r1)) * A[i];
    }
    else if(Left[1][i] != -1){
      ans += (l1-l2)*(N-i) * A[i];
    }
    else if(Left[0][i] != -1 && Right[1][i] != -1){
      ans += ((l1+1)*(r1-i) + (i-l1)*(r2-r1)) * A[i];
    }
    else if(Left[0][i] != -1 && Right[0][i] != -1){
      ans += ((l1+1)*(r1-i) + (i-l1)*(N-r1)) * A[i];
    }
    else if(Left[0][i] != -1){
      ans += (l1+1)*(N-i) * A[i];
    }
    else if(Right[1][i] != -1){
      ans += (i+1)*(r2-r1) * A[i];
    }
    else if(Right[0][i] != -1){
      ans += (i+1)*(N-r1) * A[i];
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6128