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


int main(){
  int N;
  cin >> N;
  vector<int> P(N);
  vector<int> B(N);
  for(int i = 0; i < N; ++i){
    cin >> P[i];
    --P[i];
    B[P[i]] = i;
  }
  multiset<long long> S;
  S.insert(-1);
  S.insert(-1);
  S.insert(N);
  S.insert(N);
  long long ans = 0;
  for(long long i = N-1; i >= 0; --i){
    S.insert(B[i]);
    auto itr = S.find(B[i]);
    long long n = *next(itr,1);
    long long nn = *next(itr,2);
    long long p = *prev(itr,1);
    long long pp = *prev(itr,2);
    ans += (i+1)*((nn-n)*(B[i]-p) +
                  (p-pp)*(n-B[i]));
  }
  cout << ans << endl;
}
