import java.util.TreeSet

fun main(args: Array<String>) {
    val N = readInputLine().toInt()
    val Ps = readInputLine().split(" ").map { it.toInt() }
    
    val indices = IntArray(N)
    
    for ((i, p) in Ps.withIndex()) {
        indices[p - 1] = i + 1
    }

    val biggerIndices = TreeSet<Long>()

    var ans = 0L
    
    for (i in N - 1 downTo 0) {
        val index = indices[i].toLong()
        
        val x = biggerIndices.lower(index) ?: 0L
        val w = biggerIndices.lower(x) ?: 0L
        
        val y = biggerIndices.higher(index) ?: (N + 1).toLong()
        val z = biggerIndices.higher(y) ?: (N + 1).toLong()

        ans += ((i + 1).toLong() * ((x - w) * (y - index) + (index - x) * (z - y)))

        biggerIndices.add(index)
    }
    
    println(ans)
}

fun readInputLine(): String {
    return readLine()!!
}
