class BIT
    def initialize(n)
        @n = n
        @dat = Array.new(@n, 0)
    end

    def sum(i)
        s = 0
        while i >= 0 do
            s += @dat[i]
            i = (i & (i+1)) - 1
        end
        s
    end

    def sum_between(a, b)
        sum(b) - sum(a-1)
    end

    def add(i, x)
        while i < @n do
            @dat[i] += x
            i |= i+1
        end
    end

    def lower_bound(x)
        return -1 if x <= 0
        ret = -1
        k = 1
        k <<= 1 while 2*k <= @n
        while k > 0
            if ret+k < @n && @dat[ret+k] < x
                x -= @dat[ret+k]
                ret += k
            end
            k >>= 1
        end
        ret + 1
    end
end

N = gets.to_i
P = gets.split.map(&:to_i)
pos = []
N.times do |i|
    pos[P[i]] = i
end
bit = BIT.new(N)
ans = 0
N.downto(1) do |i|
    bit.add(pos[i], 1)
    s = bit.sum(pos[i])
    l2 = bit.lower_bound(s-2)
    l1 = bit.lower_bound(s-1)
    r1 = bit.lower_bound(s+1)
    r2 = bit.lower_bound(s+2)
    ans += i * ((l1-l2)*(r1-pos[i]) + (pos[i]-l1)*(r2-r1))
end
puts ans