#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 0
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010
#define SUBMIT

template< typename SType>
class SegmentTree
{
    public:
        // 集合の要素 2 つを引数に取リ、その二項演算結果を返す関数
        using Func = function< SType(SType, SType) >;

    public:
        SegmentTree() {}
        SegmentTree(int n, const Func f, const SType &e) { Init(n, f, e); }
        // セグ木を初期化します。
        // サイズは 10^6 くらいまでならいけそう
        // n  : セグ木のサイズ
        // f  : セグ木で判定する関数
        // e : 初期値(単位元)
        void Init(int n, const Func f, const SType &e) {
            m_F = f; m_E = e;
            // 要素数は 2 のべき乗じゃないといけないのでそうする
            m_Size = 1;
            while(m_Size < n) { m_Size <<= 1; }
            m_Seg.assign(2 * m_Size, m_E);
        }

        // k 番目の要素に x をセット (0-indexed)
        void Set(int k, const SType &x) { m_Seg[k + m_Size] = x; }

        // セグ木構築 O(N)
        void Build() {
            for(int k = m_Size - 1; k > 0; k--) {
                // 子ノードに対しての演算結果を親ノードに格納
                m_Seg[k] = m_F(m_Seg[2 * k + 0], m_Seg[2 * k + 1]);
            }
        }

        // k 番目の要素を x に変更する O(log N) (0-indexed)
        // Build 後も利用可能
        void Update(int k, const SType &x) {
            k += m_Size;
            m_Seg[k] = x;
            while(k >>= 1) {
                m_Seg[k] = m_F(m_Seg[2 * k + 0], m_Seg[2 * k + 1]);
            }
        }

        // 区間 [a, b) に対して初期設定した関数をした結果を返す O(log N)
        // 開区間なので b は含まれないので注意
        // 0-indexed
        SType Query(int a, int b) {
            SType l = m_E, r = m_E;
            for(a += m_Size, b += m_Size; a < b; a >>= 1, b >>= 1) {
                if(a & 1) l = m_F(l, m_Seg[a++]);
                if(b & 1) r = m_F(m_Seg[--b], r);
            }
            return m_F(l, r);
        }

        SType operator[](const int &k) const
        {
            return m_Seg[k + m_Size];
        }
    public:
        Func m_F;               // このセグ木で処理する関数（二項演算）
        SType m_E;              // 初期値(単位元)

        int m_Size;             // セグ木の要素数
        vector< SType > m_Seg;  // セグ木本体。一次元で管理する
};

// 区間 max セグ木 seg の [lb, ub) の範囲で
// lb から右に向かってみていったときに最初に現れる val 以上の要素の
// インデックスを返す
// もし [lb, ub) の範囲に val 以上の要素がないなら、 -1 を返す
int bin_search6(SegmentTree<int>& seg, int lb, int ub, int val) {
    while(ub - lb > 1) {
        int mid = (lb + ub) / 2;
        if(seg.Query(lb, mid) >= val) { ub = mid; }
        else { lb = mid; }
    }
    return (seg.Query(lb, ub) >= val) ? lb : -1;
}

// 区間 max セグ木 seg の [lb, ub) の範囲で
// ub - 1 から左に向かってみていったときに最初に現れる val 以上の要素の
// インデックスを返す
// もし [lb, ub) の範囲に val 以上の要素がないなら、 -1 を返す
int bin_search7(SegmentTree<int>& seg, int lb, int ub, int val) {
    while(ub - lb > 1) {
        int mid = (lb + ub) / 2;
        DBG("lb: %lld ub: %lld mid: %lld\n", lb, ub, mid);
        DBG("seg.Query(mid, ub): %lld\n", seg.Query(mid, ub));
        if(seg.Query(mid, ub) >= val) { lb = mid; }
        else { ub = mid; }
    }
    return (seg.Query(lb, ub) >= val) ? lb : -1;
}

int N;
vector<int> P;


int brute_force() {
    int ret = 0;
    for(int l = 0; l < N - 1; ++l) {
        for(int r = l + 1; r < N; ++r) {
            vector<int> sub;
            for(int i = l; i <= r; ++i) { sub.push_back(P[i]); }
            SORT(sub);
            ret += sub[sub.size() - 2];
        }
    }
    return ret;
}

int solve() {
    auto Rmq = [](int a, int b) -> int
    {
        return max(a, b);
    };
    SegmentTree<int> seg;
    seg.Init(N, Rmq, -INF);
    REP(i, N) {
        seg.Set(i, P[i]);
    }
    seg.Build();

    int ret = 0;
    REP(i, N) {
        int val = P[i];
        DBG("P[%lld]: %lld = val\n", i, val);
        // i より右にあるもののうち、一番左のものを調べる
        if(i + 1 < N) {
            int r_ind = bin_search6(seg, i + 1, N, val);
            DBG("  r_ind[%lld, %lld): %lld\n", i + 1, N, r_ind);
            if(r_ind != -1) {
                // r_ind から更に右を見て、Pi が 2 番手である範囲を確定
                int r_ind2 = -1;
                if(r_ind + 1 < N) {
                    r_ind2 = bin_search6(seg, r_ind + 1, N, val);
                    if(r_ind2 != -1) { r_ind2--; }
                }
                if(r_ind2 == -1) { r_ind2 = N - 1; }
                DBG("  r_ind2: %lld\n", r_ind2);
                // i から更に左側に伸ばす場合
                int l_ind = -1;
                if(i - 1 >= 0) {
                    l_ind = bin_search7(seg, 0, i, val);
                    if(l_ind != -1) { l_ind++; }
                }
                if(l_ind == -1) { l_ind = 0; }
                DBG("  l_ind: %lld\n", l_ind);
                assert(r_ind2 >= r_ind);
                assert(i >= l_ind);
                //int cnt = (r_ind2 - r_ind) + (i - l_ind) + 1;
                int cnt = (r_ind2 - r_ind + 1) * (i - l_ind + 1);
                DBG("  cnt1: %lld\n", cnt);
                ret += val * cnt;
            }
        }
        // i より左にあるもののうち、一番右のものを調べる
        if(i - 1 >= 0) {
            int l_ind = bin_search7(seg, 0, i, val);
            DBG("  l_ind[%lld, %lld): %lld\n", 0, i, l_ind);
            if(l_ind != -1) {
                int l_ind2 = -1;
                if(l_ind - 1 >= 0) {
                    l_ind2 = bin_search7(seg, 0, l_ind, val);
                    if(l_ind2 != -1) { l_ind2++; }
                }
                if(l_ind2 == -1) { l_ind2 = 0; }
                DBG("  l_ind2: %lld\n", l_ind2);
                int r_ind = -1;
                if(i + 1 < N) {
                    r_ind = bin_search6(seg, i + 1, N, val);
                    if(r_ind != -1) { r_ind--; }
                }
                if(r_ind == -1) { r_ind = N - 1; }
                DBG("  r_ind: %lld\n", r_ind);
                assert(l_ind >= l_ind2);
                assert(r_ind >= i);
                //int cnt = (l_ind - l_ind2) + (r_ind - i) + 1;
                int cnt = (l_ind - l_ind2 + 1) * (r_ind - i + 1);
                DBG("  cnt2: %lld\n", cnt);
                ret += val * cnt;
            }
        }
    }

    return ret;
}

signed main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
#ifdef SUBMIT
    cin >> N;
    P.resize(N);
    REP(i, N) { cin >> P[i]; }
    int ans = solve();
    printf("%lld\n", ans);
#else
    N = 5;
#  if 1
    for(int i = 1; i <= N; ++i) {
        P.push_back(i);
    }
    do {
#  else
    P.push_back(1);
    P.push_back(2);
    P.push_back(3);
    P.push_back(5);
    P.push_back(4);
#  endif
        int ans = brute_force();
        int cand = solve();
        if(ans != cand) {
            printf("P: ");
            for(auto& p : P) { printf("%lld ", p); }
            printf("\n");
            printf("ans: %lld cand: %lld\n", ans, cand);
            return 0;
        }
#  if 1
    } while ( next_permutation(P.begin(), P.end()) );
#  endif

#endif

    return 0;
}


Measured memory_bytes: 3072