#include <iostream>
#include <cstdio>

using namespace std;


typedef pair<int,int> pii;

int n;
const int M = 1 << 20;
const int INF = 1e9;

struct Node
{
    int l, r;
    pii val;

    Node(int _l, int _r, int _val): l(_l), r(_r), val({_val, _val}) {};
    Node() {};
};

Node t[2 * M + 1];

void build(int x)
{
    for (int i = 0; i < M; ++i)
        t[M + i] = Node(i, i + 1, x);
    for (int i = M - 1; i > 0; --i)
        t[i] = Node(t[2 * i].l, t[2 * i + 1].r, x);
}

pii mergePairMax(pii a, pii b)
{
    if (a.second > b.second)
        swap(a, b);

    pii res;
    res.second = b.second;
    res.first = max(a.second, b.first);

    return res;
}
void updateMax(int v, int pos, int new_val)
{
    if (pos < t[v].l || t[v].r <= pos)
        return;
    if (pos == t[v].l && pos + 1 == t[v].r)
    {
        t[v].val = {-1, new_val};
        return;
    }

    updateMax(2 * v, pos, new_val);
    updateMax(2 * v + 1, pos, new_val);
    t[v].val = mergePairMax(t[2 * v].val, t[2 * v + 1].val);
}
pii getMax(int v, int l, int r)
{
    if (r <= t[v].l || t[v].r <= l)
        return {-1, -1};
    if (l <= t[v].l && t[v].r <= r)
        return t[v].val;

    pii ansL, ansR;
    ansL = getMax(2 * v, l, r);
    ansR = getMax(2 * v + 1, l, r);
    return mergePairMax(ansL, ansR);
}

pii mergePairMin(pii a, pii b)
{
    if (a.first > b.first)
        swap(a, b);

    pii res;
    res.first = a.first;
    res.second = min(a.second, b.first);

    return res;
}
void updateMin(int v, int pos, int new_val)
{
    if ((pos < t[v].l) || (t[v].r <= pos))
        return;
    if ((pos == t[v].l) && (pos + 1 == t[v].r))
    {
        t[v].val = {new_val, n};
        return;
    }

    updateMin(2 * v, pos, new_val);
    updateMin(2 * v + 1, pos, new_val);
    t[v].val = mergePairMin(t[2 * v].val, t[2 * v + 1].val);
}
pii getMin(int v, int l, int r)
{
    if (r <= t[v].l || t[v].r <= l)
        return {n, n};
    if (l <= t[v].l && t[v].r <= r)
        return t[v].val;

    pii ansL, ansR;
    ansL = getMin(2 * v, l, r);
    ansR = getMin(2 * v + 1, l, r);
    return mergePairMin(ansL, ansR);
}


const int N = 1e5;

int p[N];
pii l[N], r[N];

int main()
{
    //freopen("input.txt", "r", stdin);


    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", p + i);
        --p[i];
    }


    build(-1);

    for (int i = 0; i < n; ++i)
    {
        l[i] = getMax(1, p[i] + 1, n);
        //printf("%d %d\n", l[i].first, l[i].second);
        updateMax(1, p[i], i);
        //printf("%d %d\n", t[M + p[i]].val.first, t[M + p[i]].val.second);
    }

    build(n);

    for (int i = 0; i < n; ++i)
        updateMin(1, i, n);
    for (int i = n - 1; i >= 0; --i)
    {
        r[i] = getMin(1, p[i] + 1, n);
        updateMin(1, p[i], i);
        //printf("%d %d\n", t[M + p[i]].val.first, t[M + p[i]].val.second);
    }


    typedef long long ll;

    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        static ll cnt;
        cnt = 0;
        cnt += (r[i].first - i) * 1LL * (l[i].second - l[i].first);
        cnt += (i - l[i].second) * 1LL * (r[i].second - r[i].first);
        ans += (p[i] + 1) * cnt;
    }

    printf("%lld", ans);
}


Measured memory_bytes: 34944