#pragma GCC optimize("O3")
#pragma GCC target("sse4")

#include <bits/stdc++.h>

using namespace std;

#define GET_MACRO(_1, _2, _3, _4, NAME, ...) NAME
#define __FOR3(i, a, n, inc) for(int i = (a); (inc) > 0 ? i < (n) : i >= (n); i += (inc))
#define __FOR2(i, a, n) __FOR3(i, a, n, 1)
#define __FOR1(i, n) __FOR2(i, 0, n)
#define FOR(...) GET_MACRO(__VA_ARGS__, __FOR3, __FOR2, __FOR1)(__VA_ARGS__)

#define BOOST           ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ALL(a)          (a).begin(), (a).end()
#define SZ(a)           (int)(a).size()
#define TRAV(a, b)      for (auto& a : b)
#define REV(a)          reverse(ALL(a))
#define SORT(a)         sort(ALL(a))
#define SORTR(a)        SORT(a), REV(a)
#define PB              push_back
#define F               first
#define S               second
using ll =              long long;
using ld =              double; // 'long double' is 2.2 times slower than double
using pii =             pair<int, int>;
using pll =             pair<ll, ll>;
using vi =              vector<int>;
using vll =             vector<ll>;
using vpii =            vector<pii>;
using vpll =            vector<pll>;

template <class T> inline bool setmin(T& a, T b) {if (a > b) return a = b, 1; return 0; }
template <class T> inline bool setmax(T& a, T b) {if (a < b) return a = b, 1; return 0; }

namespace fastio {
    template <class T> istream &operator>>(istream &os, vector<T> & vec){for (auto &u : vec)os >> u;return os;}
    template <class T> ostream &operator<<(ostream &os, const vector<T> & vec){for (auto &u : vec)os << u << " ";return os;}
    template<class T1, class T2> inline istream& operator>>(istream& os, pair<T1, T2>& p) { return os >> p.first >> p.second; }
    template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << p.first << " " << p.second; }
    template <class T> ostream &operator<<(ostream &os, set<T> & con) { for (auto &u : con) os << u << " "; return os; }

    void re() {}
    template <typename T, typename... args> void re(T& x, args&... tail) { cin >> x; re(tail...); }
    void pr() {}
    template <typename T> void pr(const T& x) { cout << x; }
    template <typename T, typename... args> void pr(const T& x, const args&... tail) { cout << x << " "; pr(tail...);}
    template <typename... args> void prln(const args&... tail) { pr(tail...); cout << "\n";}
}
using namespace fastio;

namespace debug {
    template < typename _T > inline void _debug(const char *s, _T x) { cerr << s << " = " << x << "\n"; }
    template < typename _T, typename... args > void _debug(const char *s, _T x, args... a) { while(*s != ',') cerr << *s++; cerr << " = " << x << ','; _debug(s + 1, a...); }
    
    #if 0
        #define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__)
        #define cerr cout
    #else
        #define debug(...) 1999
        #define cerr if(0) cout
    #endif
}
using namespace debug;

//////////////_________CODE_________//////////////

constexpr int MOD = 1e9 + 7; // 998244353
constexpr int INF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;

const int N = 1e6 + 7;

int n;
int fen[N][2];
void upd(int x, int val, int t) {
    for(; x < n; x |= (x + 1)) {
        (t ? setmax(fen[x][t], val) : setmin(fen[x][t], val));
    }
}
int get(int x, int t) {
    int res = (t ? -1 : INF);
    for(; x >= 0; x = (x & (x + 1)) - 1) {
        (t ? setmax(res, fen[x][t]) : setmin(res, fen[x][t]));
    }
    return res;
}


int najw[2][N];
int najw2[2];

pii a[N];

int main() {
    // BOOST;

    // re(n);
    scanf("%d", &n);
    FOR(i, n) {
        // re(a[i].F);
        scanf("%d", &a[i].F);
        a[i].S = i;
        fen[i][0] = INF;
        fen[i][1] = -1;
    }

    vi Q;
    FOR(i, n) {
        while(SZ(Q) and a[Q.back()] < a[i]) {
            Q.pop_back();
        }
        najw[0][i] = (SZ(Q) ? Q.back() : -1);
        Q.PB(i);
    }

    Q.clear();
    FOR(i, n - 1, 0, -1) {
        while(SZ(Q) and a[Q.back()] < a[i]) {
            Q.pop_back();
        }
        najw[1][i] = (SZ(Q) ? Q.back() : INF);
        Q.PB(i);
    }

    sort(a, a + n, [](const pii& a, const pii& b) {
        return a > b;
    });

    ll res = 0;
    FOR(k, n) {
        auto x = a[k];

        int id = x.S;
        auto p = najw[1][id];
        if(p != INF) {
            najw[1][id] = p - 1;
            p = get(n - 1 - (p + 1), 0);
            if(p != INF) {
                najw2[1] = p - 1; 
            } else {
                najw2[1] = n - 1;
            }
        } else {
            najw[1][id] = n - 1;
            najw2[1] = -1;
        }

        auto l = najw[0][id];
        if(l != -1) {
            najw[0][id] = l + 1;
            l = get(l - 1, 1);
            if(l != -1) {
                najw2[0] = l + 1;
            } else {
                najw2[0] = 0;
            }
        } else {
            najw[0][id] = 0;
            najw2[0] = -1;
        }
        
        upd(id, id, 1);
        upd(n - 1 - id, id, 0);

        int lnajw = id - najw[0][id] + 1;
        int pnajw = najw[1][id] - id + 1;
        if(najw2[1] != -1) {
            int pnajw2 = najw2[1] - najw[1][id];
            res += 1.0 * x.F * (1ll * lnajw * pnajw2);
        }
        if(najw2[0] != -1) {
            int lnajw2 = najw[0][id] - najw2[0];
            res += 1.0 * x.F * (1ll * pnajw * lnajw2);
        }
    }

   // res /= 1.0 * n * (n - 1) / 2;

    cout << res << "\n";
}


Measured memory_bytes: 11900