#pragma GCC optimize("Ofast")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>

using namespace std;

signed main()
{
    void solve();
    void input();
    void init();

    int t = 1;

    // std::cin >> t;

    while(t--)
    {
        init();
        input();
        solve();
    }
}

int n;
int p[1 << 17];
int l[1 << 17];
int r[1 << 17];

void init()
{}

void input()
{
    std::cin >> n;
    for(int i=0; i<n; ++i) cin>>p[i];
}

#include <cassert>
#include <vector>

template <class monoid>
class segment_tree
{
    using size_type = typename std::vector<monoid>::size_type;

    class unique_queue
    {
        size_type *que, *begin, *end;
        bool *in;

    public:
        unique_queue() : que(), begin(), end(), in() {}
        unique_queue(size_type n) : que(new size_type[n]), begin(que), end(que), in(new bool[n]{}) {}
        ~unique_queue() { delete[] que; delete[] in; }

        void clear() { begin = end = que; }
        bool empty() const { return begin == end; }
        bool push(size_type index)
        {
            if(in[index]) return false;
            return in[*end++ = index] = true;
        }
        size_type pop() { return in[*begin] = false, *begin++; }
    }; // struct unique_queue

    size_type orig_n, height, ext_n;
    std::vector<monoid> data;
    unique_queue que;

    void recalc(const size_type node) { data[node] = data[node << 1] + data[node << 1 | 1]; }

    void rebuild()
    {
        while(!que.empty())
        {
            const size_type index = que.pop() >> 1;
            if(index && que.push(index)) recalc(index);
        }
        que.clear();
    }

    template <class pred_type>
    size_type right_search_subtree(size_type index, const pred_type pred, monoid mono) const
    {
        assert(index);
        while(index < ext_n)
        {
            const monoid tmp = mono + data[index <<= 1];
            if(pred(tmp)) ++index, mono = tmp;
        }
        return (index -= ext_n) < orig_n ? index : orig_n;
    }

    template <class pred_type>
    size_type left_search_subtree(size_type index, const pred_type pred, monoid mono) const
    {
        assert(index);
        while(index < ext_n)
        {
            const monoid tmp = data[(index <<= 1) | 1] + mono;
            if(pred(tmp)) mono = tmp;
            else ++index;
        }
        return ++index -= ext_n;
    }

public:
    segment_tree(const size_type n = 0)
        : orig_n{n}, height(orig_n > 1 ? 32 - __builtin_clz(orig_n - 1) : 0), ext_n{1u << height}, data(ext_n << 1), que(ext_n << 1) {}

    segment_tree(const size_type n, const monoid &init) : segment_tree(n)
    {
        std::fill(std::next(std::begin(data), ext_n), std::end(data), init);
        for(size_type i{ext_n}; --i; ) recalc(i);
    }

    template <class iter_type, class value_type = typename std::iterator_traits<iter_type>::value_type>
    segment_tree(iter_type first, iter_type last)
        : orig_n(std::distance(first, last)), height(orig_n > 1 ? 32 - __builtin_clz(orig_n - 1) : 0), ext_n{1u << height}, data(ext_n << 1), que(ext_n << 1)
    {
        static_assert(std::is_constructible<monoid, value_type>::value, "monoid(iter_type::value_type) is not constructible.");
        for(auto iter{std::next(std::begin(data), ext_n)}; iter != std::end(data) && first != last; ++iter, ++first) *iter = monoid{*first};
        for(size_type i{ext_n}; --i; ) recalc(i);
    }

    template <class container_type, typename = typename container_type::value_type>
    segment_tree(const container_type &cont) : segment_tree(std::begin(cont), std::end(cont)) {}

    // reference to the element at the index.
    typename decltype(data)::reference operator[](size_type index)
    {
        assert(index < orig_n);
        que.push(index |= ext_n);
        return data[index];
    }

    // const reference to the element at the index.
    typename decltype(data)::const_reference operator[](size_type index) const
    {
        assert(index < orig_n);
        return data[index |= orig_n];
    }

    monoid fold(size_type first, size_type last)
    {
        assert(last <= orig_n);
        rebuild();
        monoid leftval{}, rightval{};
        first += ext_n, last += ext_n;
        while(first < last)
        {
            if(first & 1) leftval = leftval + data[first++];
            if(last & 1) rightval = data[--last] + rightval;
            first >>= 1, last >>= 1;
        }
        return leftval + rightval;
    }

    monoid fold() { return fold(0, orig_n); }

    template <class pred_type>
    size_type left_search(size_type right, const pred_type pred)
    {
        assert(right <= orig_n);
        rebuild();
        right += ext_n;
        monoid mono{};
        for(size_type left{ext_n}; left != right; left >>= 1, right >>= 1)
        {
            if((left & 1) != (right & 1))
            {
                const monoid tmp = data[--right] + mono;
                if(!pred(tmp)) return left_search_subtree(right, pred, mono);
                mono = tmp;
            }
        }
        return 0;
    }

    template <class pred_type>
    size_type right_search(size_type left, const pred_type pred)
    {
        assert(left <= orig_n);
        rebuild();
        left += ext_n;
        monoid mono{};
        for(size_type right{ext_n << 1}; left != right; left >>= 1, right >>= 1)
        {
            if((left & 1) != (right & 1))
            {
                const monoid tmp = mono + data[left];
                if(!pred(tmp)) return right_search_subtree(left, pred, mono);
                mono = tmp;
                ++left;
            }
        }
        return orig_n;
    }
}; // class segment_tree

void solve()
{
    for(int i = 0, t = 0, stk[1 << 17]; i < n; i++)
    {
        while(t and p[stk[t - 1]] < p[i])
        {
            t--;
        }
        l[i] = t ? stk[t - 1] : -1;
        stk[t++] = i;
    }

    for(int i = n - 1, t = 0, stk[1 << 17]; i >= 0; i--)
    {
        while(t and p[stk[t - 1]] < p[i])
        {
            t--;
        }
        r[i] = t ? stk[t - 1] : n;
        stk[t++] = i;
    }

    struct mano
    {
        int val=0;
        mano() {}
        mano(int v) : val(v) {}
        mano operator+(mano const& rhs) const
        {
            return val>rhs.val ? *this : rhs;
        }
    };

    segment_tree<mano> seg_max(p, p + n);

    long long ans = 0;
    for(int i = 0; i < n; i++)
    {
        int lll =
            ~l[i] ? seg_max.left_search(l[i], [&](mano x) { return x.val <= p[i]; })-1
                : -1;
        int rrr = r[i] < n ? seg_max.right_search(
                                r[i]+1, [&](mano x) { return x.val <= p[i]; })
                        : n;
        ans += (long long)p[i] * (l[i] - lll) * (r[i] - i);
        ans += (long long)p[i] * (rrr - r[i]) * (i - l[i]);
    }
    std::cout << ans << "\n";
}


Measured memory_bytes: 3072