#include <bits/stdc++.h>

using namespace std;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);

  int N;
  cin>>N;
  vector<int> P(N);
  for (auto& p : P) cin>>p;

  vector<int> id(N);
  iota(id.begin(), id.end(), 0);
  sort(id.begin(), id.end(), [&](int l, int r) {
    return P[l] > P[r];
  });

  long ans = 0;
  multiset<int> pset={-1,-1,N,N};
  for (int i = 0; i < N; i++) {
    auto ii = id[i];
    auto l2i = --pset.lower_bound(ii);
    int l2 = *l2i;
    int l1 = *(--l2i);
    auto r1i = pset.upper_bound(ii);
    int r1 = *r1i;
    int r2 = *(++r1i);
    ans += (long)P[ii] * ((l2-l1)*(r1-ii) + (ii-l2)*(r2-r1));
    pset.insert(ii);
  }
  cout << ans << endl;

  return 0;
}
