#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main() {
  int N;
  cin >> N;
  vector<pair<int, int>> P(N);
  for (int i = 1; i <= N; i++) {
    int p;
    cin >> p;
    P[i - 1] = make_pair(p, i);
  }
  sort(P.begin(), P.end(), greater<pair<int, int>>());

  ll ans = 0;
  multiset<ll> S = {0, 0, N + 1, N + 1};
  S.insert(P[0].second);
  for (int i = 1; i < N; i++) {
    int p = P[i].second;
    S.insert(p);
    auto it = S.find(p);
    ll r1 = *next(it);
    ll r2 = *next(next(it));
    ll l1 = *prev(it);
    ll l2 = *prev(prev(it));
    ans += ((r2 - r1) * (p - l1) + (l1 - l2) * (r1 - p)) * P[i].first;
  }
  cout << ans << endl;
}
