// PDF解説に倣って。
#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,a;
  cin>> n;
  vector<int> index(n);
  for (int i=0; i<n; i++){
    cin>> a;
    index[n-a]=i;
  }
  
  
  int64_t ans=0,num,le,l,r,re;
  multiset<int> s;
  s.insert(-1); s.insert(-1); s.insert(n); s.insert(n);
  for (int i=0; i<n; i++){
    num=index[i];
    auto itr=s.lower_bound(num); //ひょっとするとここの書き方？
    r=*itr++;
    re=*itr--;itr--;
    l=*itr--;
    le=*itr;
    ans+=(n-i)*((l-le)*(r-num)+(num-l)*(re-r));
    s.insert(num);
  }
  cout<< ans << endl;
}
/*TLEは台風のせいではありません*/