import std.algorithm;
import std.bigint;
import std.concurrency;
import std.container;
import std.conv;
import std.functional;
import std.format;
import std.math;
import std.meta;
import std.numeric;
import std.random;
import std.range;
import std.stdio;
import std.string;
import std.traits;
import std.typecons;


auto solve(long N, long[] P) {
    const DUMMY = -1;
    
    P = DUMMY ~ P ~ DUMMY;
    auto rSight = iota(1, N + 3).array;
    auto lSight = iota(-1, N + 1).array;
    auto indiceOrder = P.enumerate
        .array
        .sort!"a[1] < b[1]"
        .map!"a[0]"
        .drop(2)
        .take(N - 1);
    
    long ans;
    foreach (i; indiceOrder) {
        long waysToMakeRange;
        if (0 < lSight[i] && lSight[i] < N + 1)
            waysToMakeRange += (lSight[i] - lSight[lSight[i]]) * (rSight[i] - i);
        if (0 < rSight[i] && rSight[i] < N + 1)
            waysToMakeRange += (rSight[rSight[i]] - rSight[i]) * (i - lSight[i]);
        
        ans += P[i] * waysToMakeRange;

        rSight[lSight[i]] = rSight[i];
        lSight[rSight[i]] = lSight[i];
    }

    return ans;
}


void main() {
    auto input = stdin.byLine.map!split.joiner;

    long N;
    N = input.front.to!long;
    input.popFront;

    long[] P = new long[](cast(size_t) (N));
    foreach (i; 0 .. cast(size_t) (N)) {
        P[i] = input.front.to!long;
        input.popFront;
    }

    static if (is(ReturnType!solve == void))
        solve(N, P);
    else
        solve(N, P).writeln;
}
