#pragma comment(linker, "/STACK:1024000000,1024000000")
#pragma GCC optimize("Ofast", "unroll-loops")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

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

int n, a[100005];
multiset<int> st;
int main() {
  scanf("%d", &n);
  for (int i = 1, x; i <= n; ++i)
    scanf("%d", &x), a[x] = i;
  st.insert(0);
  st.insert(0);
  st.insert(n + 1);
  st.insert(n + 1);
  long long ans = 0;
  for (int i = n; i >= 1; --i) {
    auto it = st.lower_bound(a[i]);
    auto nxt = it; nxt++;
    auto prv = it; prv--;
    auto prvv = prv; prvv--;
    ans += 1LL * i * ((*nxt - *it) * (a[i] - *prv) + (*prv - *prvv) * (*it - a[i]));
    st.insert(a[i]);
  }
  printf("%lld\n", ans);
  return 0;
}
