#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
template<class T, class Compare = less<T> >
using MaxHeap = priority_queue<T, vector<T>, Compare>;
template<class T, class Compare = greater<T> >
using MinHeap = priority_queue<T, vector<T>, Compare>;
using llong = long long;

//===
template<typename Monoid>
struct SegmentTree {
    using OP = function<Monoid(Monoid, Monoid)>;
    
    vector<Monoid> tree;
    int size;
    const OP f; // bin' operation
    const Monoid e; // neutral element
                                           
    SegmentTree(int nmemb, const Monoid &e, const OP &f):
        f(f),
        e(e)
    {
        size = 1;
        while (size < nmemb) {
            size *= 2;
        }

        tree.assign(2 * size - 1, e);
    }

    void update(int k, Monoid dat) {
        k += size - 1;
        tree[k] = dat;
        
        while(k > 0) {
            k = (k - 1) / 2;
            tree[k] = f(tree[2 * k + 1], tree[2 * k + 2]);
        }
    }

    // [l, r)
    Monoid query(int l, int r) {
        l += size - 1;
        r += size - 1;

        Monoid d = e;
        while (l < r) {
            if (l % 2 == 0) {
                d = f(d, tree[l]);
                l++;
            }
            if (r % 2 == 0) {
                r--;
                d = f(d, tree[r]);
            }

            l = (l - 1) / 2;
            r = (r - 1) / 2;
        }

        return d;
    }

    Monoid operator[] (const int k) { return query(k, k + 1); }
};
//===

struct M {
    llong v;
    llong idx;

    M (llong v, llong idx): v(v), idx(idx) {};
};

llong n;
llong p[100005];
pair<llong, llong> range[100005];
llong sum;

int main() {
    cin >> n;

    SegmentTree<M>seg(n, M(-1, -1),
                  [](M l, M r){
                      if (l.v > r.v) return l;
                      else return r;
                  });

    llong mv = 0;
    for (int i = 0; i < n; i++) {
        cin >> p[i];

        mv = max(mv, p[i]);
        seg.update(i, M(p[i], i));
    }

    for (int i = 0; i < n; i++) {

        llong l, r;
        //left
        {
            llong valid = i;
            llong invalid = -1;

            while (valid - invalid > 1) {
                llong mid = (valid + invalid) / 2;

                if (seg.query(mid, i).v > p[i]) {
                    invalid = mid;
                }
                else {
                    valid = mid;
                }
            }

            l = valid - 1;
        }
        //right
        {
            llong valid = i + 1;
            llong invalid = n + 1;

            while (invalid - valid > 1) {
                llong mid = (valid + invalid) / 2;

                if (seg.query(i + 1, mid).v > p[i]) {
                    invalid = mid;
                }
                else {
                    valid = mid;
                }
            }

            r = valid;
        }

        range[i] = make_pair(l, r);
    }

    for (llong i = 0; i < n; i++) {
        if (mv == p[i]) continue;
        
        llong l, r, ml, mr;
        ml = range[i].first;
        mr = range[i].second;
        l = ml;
        r = mr;

        
        if (mr < n) {
            // right;
            seg.update(mr, M(-1, -1));
            llong valid = mr;
            llong invalid = n + 1;
            while (invalid - valid > 1) {
                llong mid = (valid + invalid) / 2;

                if (seg.query(i, mid).v > p[i]) {
                    invalid = mid;
                }
                else {
                    valid = mid;
                }
            }
            
            r = valid;
            seg.update(mr, M(p[mr], mr + 1));
        }

        if (ml >= 0) {
            // left;
            seg.update(ml, M(-1, -1));
            llong valid = i;
            llong invalid = -1;
            while (valid - invalid > 1) {
                llong mid = (valid + invalid) / 2;

                if (seg.query(mid, i).v > p[i]) {
                    invalid = mid;
                }
                else {
                    valid = mid;
                }
            }
            l = valid - 1;
            seg.update(ml, M(p[ml], ml - 1));
        }

        llong mul = 0;

        // printf("%lld: [%lld, %lld, %lld, %lld] ", p[i], l, ml, mr, r);

        mul = (r - mr) * (i - ml) + (mr - i) * (ml - l);
        sum += mul * p[i];
        //        cout << sum << endl;
    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 6656