#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <array>
#include <list>
#include <forward_list>
#include <complex>
#include <numeric>
#include <regex>
#include <boost/optional.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <boost/range/irange.hpp>

using namespace std;

//#define int mnt
#define let const auto&
#define var auto&&

using mnt = int_fast64_t;

using ll = long long;
using ld = long double;

template<typename T=int> using vec = vector<T>;
template<typename T=int> using mat = vec<vec<T>>;
template<typename T=int> using dic = map<string, T>;
template<typename T=int> using dict = unordered_map<string, T>;
template<typename T=int> using pqg = priority_queue<T, vector<T>, greater<T>>;
template<typename T=int, class F=less<T>> using pq = priority_queue<T, vector<T>, greater<T>>;

using pii = pair<int, int>;
using vi = vector<int>;
using mi = vector<vector<int>>;
using vp = vector<pii>;
using vb = vector<bool>;

template<typename T=int> using opt = boost::optional<T>;
//using cint = boost::multiprecision::cpp_int;
//using boost::irange;

constexpr int IINF = 0x3f3f3f3f;
constexpr mnt LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int INF = (int)LINF;

constexpr mnt MOD = 1e9+7;

#define _overload(_1,_2,_3,_4,name,...) name
#define _rep1(n) for(int i=0,i_=(n);i<i_;++i)
#define _rep2(i,n) for(int i=0,_##i=(n);i<_##i;++i)
#define _rep3(i,a,b) for(int i=(a),_##i=(b);i<_##i;++i)
#define _rep4(i,a,b,c) for(int i=(a),_##i=(b),__##i=(c);i<_##i;i+=__##i)
#define rep(...) _overload(__VA_ARGS__,_rep4,_rep3,_rep2,_rep1)(__VA_ARGS__)
#define _rrep1(n) for(int i=(n)-1;i>=0;--i)
#define _rrep2(i,n) for(int i=(n)-1;i>=0;--i)
#define _rrep3(i,a,b) for(int i=(b)-1,_##i=(a);i>=_##i;--i)
#define _rrep4(i,a,b,c) for(int i=((b)-(a)-1)/(c)*(c)+(a),_##i=(a),__##i=(c);i>=_##i;i-=__##i)
#define rrep(...) _overload(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__)

#define eb emplace_back
#define pb push_back
#define pob pop_back
#define puf push_front
#define pof pop_front

#define np next_permutation
#define pp prev_permutation

#define mp make_pair
#define mt make_tuple
#define fat forward_as_tuple

#define ft first
#define sd second

#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)

#define elif else if
#define unless(a) if(!(a))
#define qt(a) #a

#define endl '\n'
#define deci(n) fixed << setprecision(n)
#define zfl(n) setfill(‘0’) << setw(n)

template<typename T=int, class C> inline constexpr T sz(const C& a) { return (T)a.size(); };
template<class C> inline constexpr C& rev(C& a) { reverse(begin(a), end(a)); return a; }
template<class C> inline constexpr C rev(C&& a) { C b = a; return rev(b); }
template<class C> inline constexpr C& sort(C& a) { sort(begin(a), end(a)); return a; }
template<class C> inline constexpr C sort(C&& a) { C b = a; return sort(b); }
template<class C, typename T> inline constexpr bool bs(const C& a, const T& v) { return binary_search(begin(a), end(a), v); }
template<class C, typename T> inline constexpr auto lb(const C& a, const T& v) { return lower_bound(begin(a), end(a), v); }
template<class C, typename T> inline constexpr auto ub(const C& a, const T& v) { return upper_bound(begin(a), end(a), v); }
template<class C> inline constexpr auto& min(const C& a) { return *min_element(begin(a), end(a)); }
template<class C> inline constexpr auto& max(const C& a) { return *max_element(begin(a), end(a)); }
template<typename T> inline constexpr void rs(vector<T>& a, size_t n) { a.resize(n); }
template<class C> inline constexpr auto sum(const C& c) { return accumulate(next(begin(c)), end(c), *begin(c)); }
template<class C, class F> inline constexpr auto foldl(const C& c, const F& f) { return accumulate(next(begin(c)), end(c), *begin(c), f); }

template<typename T> inline constexpr T gcd2(T a, T b) { if(a==0 || b==0) return 0; while(b) { a = a%b; swap(a, b); } return a; }
template<typename T> inline constexpr T extgcd2(T a, T b, T& x, T& y) { x = 1; y = 0; while (b) { T t = a / b; a -= t * b; swap(a, b); x -= t * y; swap(x, y); } return a; }
template<typename T> inline constexpr T lcm(T a, T b) { return a / gcd2(a, b) * b; }

template<typename T> inline constexpr bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline constexpr bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } return false; }

template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first; is >> p.second; return is; }
template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.first << ' ' << p.second; return os; }

template<typename T> istream& operator>>(istream& is, vector<T>& v) { for(auto&& x : v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { for(size_t i=0;i<v.size();++i) { if(i>0) os << ' '; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) { for(size_t i=0;i<v.size();++i) { if(i>0) os << '\n'; os << v[i]; } return os; }


#define make_v(T,...) __make_v<T>(__VA_ARGS__)
template <typename T> auto __make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts> auto __make_v(size_t a, Ts... ts) { return vector<decltype(__make_v<T>(ts...))>(a, __make_v<T>(ts...)); }

template<typename T> struct has_itr {
  template<typename U> static auto check(U x) -> decltype(begin(x), end(x), true_type()); static false_type check(...);
  static bool constexpr value = decltype( check( declval<T>() ) )::value;
};
template <typename T, typename V, enable_if_t<!has_itr<T>::value, nullptr_t> = nullptr> void fill_v(T& t, const V& v) { t = v; }
template <typename T, typename V, enable_if_t< has_itr<T>::value, nullptr_t> = nullptr> void fill_v(T& t, const V& v) { for(auto&& e : t) fill_v(e, v); }
template <typename T, class F, enable_if_t<!has_itr<T>::value, nullptr_t> = nullptr> inline constexpr T& apply(T& t, const F& f) { return t = f(t); }
template <typename T, class F, enable_if_t< has_itr<T>::value, nullptr_t> = nullptr> inline constexpr auto& apply(T& t, const F& f) { for(auto&& e : t) apply(e, f); return t; }
template <typename T, class F, enable_if_t< has_itr<T>::value, nullptr_t> = nullptr> inline constexpr auto apply(T&& t, const F& f) { auto u = t; return apply(u, f); }

template <typename T> struct is_pair : false_type {}; template <typename T, typename U> struct is_pair<pair<T, U>> : true_type {};
template<typename T, enable_if_t<!is_pair<T>::value, nullptr_t> = nullptr> inline constexpr T& dcr(T& t) { return --t; }
template<typename T, enable_if_t< is_pair<T>::value, nullptr_t> = nullptr> inline constexpr T& dcr(T& t) { --t.ft; --t.sd; return t; }

template<typename T> struct is_priority_queue : false_type {}; template<typename T, class V, class C> struct is_priority_queue<priority_queue<T, V, C>> : true_type {};
template<typename T, enable_if_t< is_priority_queue<T>::value, nullptr_t> = nullptr> inline constexpr auto pop_front(T& p) { auto q = p.top(); p.pop(); return q; }

struct InitIO {
  InitIO() {
    cin.tie(nullptr); cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    #ifndef LOCAL
      cerr.rdbuf(nullptr);
    #endif
  }

} initio;
#ifdef LOCAL
  #include <boost/type_index.hpp>
  #define trace(...) __trace(" " #__VA_ARGS__ ",", __VA_ARGS__)
  template <typename T> inline constexpr const char* __trace(const char* n, const T& t)
  { const char* c = strchr(n+1, ','); cerr.write(n, c-n) << " = " << t << "; // " << boost::typeindex::type_id_with_cvr<decltype(t)>().pretty_name() <<"\n"; return c; }
  template <typename T, typename... Ts> inline constexpr const char* __trace(const char* n, const T& t, const Ts&... ts)
  { const char* c = __trace(n, t); return __trace(c+1, ts...); }
#else
  #define trace(...)
#endif

#define in(T,...) __in<T>(__VA_ARGS__)
template<typename T> inline void sc(T& x) { cin >> x; }
template<typename T, typename... Ts> inline void sc(T& t, Ts&... ts) { sc(t); sc(ts...); }
template<typename T=int> inline T __in() { T x; sc(x); return x; }
template<typename T, typename... Ts> inline auto __in(Ts ...ts) { auto v = __make_v<T>(ts...); sc(v); return v; }
inline string input() { string str; cin >> ws; getline(cin, str); return str; }
template<typename T> inline void out(const T& x) { cout << x; }
template<typename T, typename... Ts> inline void out(const T& t, const Ts&... ts) { out(t); out(' '); out(ts...); }
template<typename T> inline void err(const T& x) { cerr << x; }
template<typename T, typename... Ts> inline void err(const T& t, const Ts&... ts) { err(t); err(' '); err(ts...); }
template<typename... Ts> inline void print(const Ts&... ts) { out(ts...); out('\n'); }
template<typename... Ts> inline void debug(const Ts&... ts) { err(ts...); err('\n'); }

inline constexpr auto yes(const bool& c) { return c ? "yes" : "no"; }
inline constexpr auto Yes(const bool& c) { return c ? "Yes" : "No"; }
inline constexpr auto YES(const bool& c) { return c ? "YES" : "NO"; }
inline constexpr auto pos(const bool& c) { return c ? "possible" : "impossible"; }
inline constexpr auto Pos(const bool& c) { return c ? "Possible" : "Impossible"; }
inline constexpr auto POS(const bool& c) { return c ? "POSSIBLE" : "IMPOSSIBLE"; }

constexpr int lim = 1e5+7;


signed main() {

  let N = in();
  let P = in(int, N);
  var Q = make_v(int, N+1);
  rep(i, N) Q[P[i]] = i+1;

  mnt ans = 0, v;

  multiset<int> C;
  C.insert(0); C.insert(0);
  C.insert(N+1); C.insert(N+1);
  C.insert(Q[N]);
  int L1, L2, R1, R2;
  rrep(i, 1, N) {
    C.insert(Q[i]);
    auto it = C.find(Q[i]);

    v = 0;

    auto pi = prev(it); L1 = *pi;
    --pi; L2 = *pi;
    auto ni = next(it); R1 = *ni;
    ++ni; R2 = *ni;

    if(L1 > 0) v += (R1-Q[i])*(L1-L2);
    if(R1 <= N) v += (Q[i]-L1)*(R2-R1);

    debug("i =", i);
    debug(L2, L1, Q[i], R1, R2);
    debug("v =", v);

    ans += v*i;
  }
  print(ans);

  #ifdef LOCAL
  ans = 0;
  rep(i, N) {
    rep(j, i+1, N) {
      int M = max(P[i], P[i+1]), M2 = min(P[i], P[i+1]);
      rep(k, i+2, j+1) {
        if(P[k] > M) M2 = M, M = P[k];
        else if(P[k] > M2) M2 = P[k];
      }
      ans += M2;
    }
  }
  debug(ans);
  #endif

  return 0;
}


Measured memory_bytes: 5760