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

int main(){
  int N; cin >> N;
  vector<int> nlis(N);
  int foo;

  for (int i = 0; i < N; i++){
    cin >> foo;
    nlis[N-foo] = i;
  }

  vector<int> bis = {-1,-1,N,N};
  long long ans = 0;
  vector<int>::iterator inser;
  long long a,b,c,d,e;

  for (int i = 0; i < N; i++){
    inser = lower_bound(bis.begin(),bis.end(),nlis[i]);
    c = nlis[i];
    b = *(--inser);
    a = *(--inser);
    ++inser;
    d = *(++inser);
    e = *(++inser);
    --inser;
    bis.insert(inser,nlis[i]);

    a = (e-d)*(c-b) +(d-c)*(b-a);

    ans += a*(N-i);
  }
  cout << ans << endl;
}
