#include<bits/stdc++.h>
using namespace std;

struct Node
{
    int l, r;
    int mi, ma;
    Node *lnode, *rnode;
    
    Node(int l, int r) : l(l), r(r), mi(1000000), ma(-1)
    {
        if (r - l != 1)
        {
            lnode = new Node(l, l + r >> 1);
            rnode = new Node(l + r >> 1, r);
        }
    }
    
    int min_query(int L, int R)
    {
        if (R <= l || r <= L)
            return 1000000;
        else if (L <= l && r <= R)
            return mi;
        else
            return min(lnode->min_query(L, R), rnode->min_query(L, R));
    }
    
    int max_query(int L, int R)
    {
        if (R <= l || r <= L)
            return -1;
        else if (L <= l && r <= R)
            return ma;
        else
            return max(lnode->max_query(L, R), rnode->max_query(L, R));
    }
    
    void update(int idx, int v)
    {
        if (r - l == 1)
        {
            mi = v;
            ma = v;
        }
        else
        {
            if (idx < lnode->r)
                lnode->update(idx, v);
            else
                rnode->update(idx, v);
            mi = min(lnode->mi, rnode->mi);
            ma = max(lnode->ma, rnode->ma);
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i != n; ++i)
        cin >> arr[i];
    
    vector<int> lef(n);
    vector<int> lef2(n);
    Node *ltree = new Node(0, n);
    for (int i = 0; i != n; ++i)
    {
        int qry = ltree->max_query(arr[i], n);
        if (qry == -1)
            lef[i] = 0;
        else
        {
            lef[i] = i - qry;
            
            int tmp = ltree->max_query(arr[i], arr[qry] - 1);
            int qry2 = ltree->max_query(arr[qry], n);
            qry2 = max(qry2, tmp);
            
            if (qry2 == -1)
                lef2[i] = 0;
            else
                lef2[i] = qry - qry2; 
        }
        
        ltree->update(arr[i] - 1, i);
    }
    
    vector<int> rig(n);
    vector<int> rig2(n);
    Node *rtree = new Node(0, n);
    for (int i = n - 1; i != -1; --i)
    {
        int qry = rtree->min_query(arr[i], n);
        if (qry == 1000000)
            rig[i] = 0;
        else
        {
            rig[i] = qry - i;
            
            int tmp = rtree->min_query(arr[i], arr[qry] - 1);
            int qry2 = rtree->min_query(arr[qry], n);
            qry2 = min(qry2, tmp);
            
            if (qry2 == 1000000)
                rig2[i] = 0;
            else
                rig2[i] = qry2 - qry; 
        }
        
        rtree->update(arr[i] - 1, i);
    }
    
    long long ans = 0;
    for (int i = 0; i != n; ++i)
    {
        if (arr[i] == n)
            continue;
        
        long long mult = arr[i];
        
        if (lef[i] == 0)
        {
            if (rig2[i])
                ans += mult * (i + 1) * (rig2[i]);
            else
                ans += mult * (i + 1) * (n - (i + rig[i]));
        }
        else if (rig[i] == 0)
        {
            // if (i == 2)
            //     cout << lef2[i] << ' ' << lef[i] << '\n';;
            if (lef2[i])
                ans += mult * (lef2[i]) * (n - i);
            else
                ans += mult * (i - lef[i] + 1) * (n - i);
        }
        else
        {
            if (lef2[i])
                ans += mult * (lef2[i]) * (rig[i]);
            else
                ans += mult * (i - lef[i] + 1) * (rig[i]);
            if (rig2[i])
                ans += mult * (lef[i]) * (rig2[i]);
            else
                ans += mult * (lef[i]) * (n - (i + rig[i]));
        }
    }
    
    cout << ans << '\n';
    
    return 0;
}


Measured memory_bytes: 20992