#include <iostream>
#include <set>
using namespace std;

int main() {
  int n;
  cin >> n;
  int idx[n - 1];
  for (int i = 0; i < n; i++) {
    int tmp;
    cin >> tmp;
    idx[tmp - 1] = i;
  }
  multiset <int> s;
  s.insert(-1);
  s.insert(-1);
  s.insert(n);
  s.insert(n);
  s.insert(idx[n - 1]);
  long long int ans = 0;
  for (int i = n - 2; i >= 0; i--) {
    auto itr = s.upper_bound(idx[i]);
    long long int r1 = *itr;
    itr++;
    long long int r2 = *itr;
    itr--;
    itr--;
    long long int l1 = *itr;
    itr--;
    long long int l2 = *itr;
    ans += (i + 1) * ((l1 - l2) * (r1 - idx[i]) + (idx[i] - l1) * (r2 - r1));
    s.insert(idx[i]);
  }
  printf("%lld\n", ans);
  return 0;
}
