#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

signed main(){

  int n; cin >> n;
  vector<int> p(n),order(n);
  for(int i = 0; i < n; i++){
    cin >> p[i];
    p[i]--;
    order[p[i]] = i;
  }

  multiset<int> st;
  st.insert(-1);
  st.insert(-1);
  st.insert(n);
  st.insert(n);
  int ans = 0;
  for(int i = n-1; i >= 0; i--){
    auto p = st.lower_bound(order[i]);
    int r = *p++;
    int rr = *p--;
    p--;
    int l = *p--;
    int ll = *p;
    int res = (order[i] - l) * (rr - r) + (r - order[i]) * (l - ll);
    ans = (ans + res * (i+1));
    st.insert(order[i]);
  }
  cout << ans << endl;

  return 0;
}
