#include <bits/stdc++.h>
using namespace std;

void solve(istream& cin, ostream& cout) {
  int n;
  int p;
  cin >> n;
  vector<int> idx(n + 1);

  for (int i = 1; i <= n; i++) {
    cin >> p;
    idx[p] = i;
  }

  multiset<int> upper{0, 0, n + 1, n + 1};

  long long ans = 0;
  for (int v = n; v >= 1; v--) {
    int i = idx[v];
    long long w, x, y, z;
    upper.insert(i);
    auto itr = upper.find(i);
    x = *(--itr);
    w = *(--itr);
    itr = upper.find(i);
    y = *(++itr);
    z = *(++itr);

    ans += ((x - w) * (y - i) + (i - x) * (z - y)) * v;
  }
  cout << ans << endl;
}

#ifndef TEST
int main() {
  solve(cin, cout);
}
#endif
