// Code by H~$~C
#warning "Code by H~$~C, don't copy it!"
#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")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define rint register int
#define inline __attribute__((always_inline)) inline
#define rep(i, n) for (rint i = 0; i < (n); ++i)
#define rep1(i, n) for (rint i = (1); i <= (n); ++i)
#define Rep(i, a, b) for (rint i = (a); i <= (b); ++i)
#define per(i, n) for (rint i = ((n) - 1); ~i; --i)
#define per1(i, n) for (rint i = (n); i; --i)
#define Per(i, a, b) for (rint i = (a); i >= (b); --i)
#define eprintf(...) (fprintf(stderr, __VA_ARGS__) & fflush(stderr))
#define fillset(a, val) memset(a, val, sizeof(a))
#define All(a) a.begin(), a.end()
#define SZ(a) ((int)a.size())
#define cast(type, y) static_cast<type>(y)
#define fi first
#define se second
#define endl '\n'
using namespace std;
#ifndef LOCAL_JUDGE
static bool local_judge = false;
#define Debug(...)
#else
static bool local_judge = true;
template<typename T> inline void _debug(const char *names, T &&t) { (cerr << names << " = " << t << endl).flush();}
template<typename T, typename ...Args> inline void _debug(const char *names, T &&t1, Args &&...t) {
const char *comma = strchr(names, ','); (cerr.write(names, comma - names) << " = " << t1 << ", ").flush(); _debug(comma + 1, t...);}
#define Debug(...) _debug(#__VA_ARGS__, __VA_ARGS__)
#endif
using ll = long long; using ull = unsigned long long; using uint = unsigned; using llf = long double; using pil = pair<int, ll>; using pii = pair<int, int>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using vi = vector<int>; using vl = vector<ll>; using vs = vector<string>;
template<typename T> using min_queue = priority_queue<T, vector<T>, greater<T> >; template<typename T> using max_queue = priority_queue<T>;
template<typename T> inline void reinit(T &t) { t.~T(); new (&t) T(); }
template<typename T> inline T chmax(T &x, T y) { return x = max(x, y); } template<typename T> inline T chmin(T &x, T y) { return x = min(x, y); }
template<typename T> inline T fadd(T x, T y, T mod) { return (x += y) >= mod ? x - mod : (x < 0 ? x + mod : x); }
inline int fmul(int x, int y, int mod) { return 1LL * x * y - 1LL * x * y / mod * mod; } inline ll fmul(ll x, ll y, ll mod) { return (x * y - (ll)((long double)x / mod * y) * mod + mod) % mod; }
template<typename T> inline T modpower(T x, ll y, const T &mod) { T res(1); for (; y; x = fmul(x, x, mod), y >>= 1) if (y & 1) res = fmul(res, x, mod); return res; }
template<typename T> inline string to_string(const vector<T> &v) { string res; for (auto &x: v) res += to_string(x), res += ' '; res.pop_back(); return res; } inline string to_string(const string &x) { return x; } inline string to_string(const char *x) { return string(x); }
inline string format(const string &x) { return x; } template<typename T, typename ...Args> string format(const string &fmt, const T &x, const Args &...y) { string res; int len = (int)fmt.size(), flag = 0; for (int i = 0; i < len - 1; ++i) if (fmt[i] == '{' && fmt[i + 1] == '}') { if (i == len - 1) { flag = 1; res += to_string(x); return res; } if (sizeof...(y) == 0) return res + to_string(x) + fmt.substr(i + 2); string rest = format(fmt.substr(i + 2), y...); return res + to_string(x) + rest; } else res += fmt[i]; }
template<typename T, typename ...Args> string format(const char *fmt, const T &x, const Args &...y) { return format(string(fmt), x, y...); }
#define coutf(...) (cout << format(__VA_ARGS__), 1)
inline void print_time() { eprintf("\n\nTime: %.3f ms\n\n\n", clock() * 1000.0 / CLOCKS_PER_SEC); }
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
const ll inf = 0x3f3f3f3f, lnf = 0x3f3f3f3f3f3f3f3f;
const int mod1 = 1000000007, mod2 = 998244353, mod3 = 1000000009;
const double EPS = 1e-9, PI = acos(-1.0), _E_ = exp(1.0);

int n, a[100005];
int main(int argc, const char *argv[]) {
  srand(88150980479857814273); // a big prime
  if (__builtin_expect(local_judge, false)) atexit(print_time);
  cerr << "Code by H~$~C: \n" << flush;
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(12);
  cin >> n;
  rep1(i, n) {
    int x;
    cin >> x;
    a[x] = i;
  }
  multiset<int> st;
  st.insert(0);
  st.insert(0);
  st.insert(n + 1);
  st.insert(n + 1);
  ll ans = 0; 
  per1(i, n) {
    auto it = st.lower_bound(a[i]);
    auto nxt = it; nxt++;
    auto prv = it; prv--;
    auto prvv = prv; prvv--;
    ans += cast(ll, i) * ((*nxt - *it) * (a[i] - *prv) + (*prv - *prvv) * (*it - a[i]));
    st.insert(a[i]);
  }
  coutf("{}\n", ans);
  return 0;
}


Measured memory_bytes: 5376