import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.container, std.range;

alias P = Tuple!(long, "i", long, "p");

void main()
{
    auto N = readln.chomp.to!long;
    P[] ps;
    foreach (i, p; readln.split.to!(long[])) ps ~= P(i.to!long+1, p);
    sort!"a.p > b.p"(ps);
    auto T = redBlackTree(0, ps[0].i, N+1);
    long res;
    foreach (i; 1..N) {
        auto p = ps[i].p;
        auto x = ps[i].i;
        {
            auto l = x;
            auto r = T.upperBound(x).front;
            if (r != N+1) {
                auto ll = T.lowerBound(l).back;
                auto rr = T.upperBound(r).front;
                res += (l-ll) * (rr-r) * p;
            }
        }
        {
            auto r = x;
            auto l = T.lowerBound(x).back;
            if (l != 0) {
                auto ll = T.lowerBound(l).back;
                auto rr = T.upperBound(r).front;
                res += (l-ll) * (rr-r) * p;
            }
        }
        T.insert(x);
    }
    writeln(res);
}