import java.util.*
import java.io.PrintWriter


class P(idx: Int, x: Int) {
    val idx = idx
    val x = x
}

fun calc(l2: Int, l1: Int, r1: Int, r2: Int): Int {
    return (l2 - l1)*r1 + (r2 - r1)*(l1)
}
fun main(args: Array<String>){
	val cin = Scanner(System.`in`)
    val cout = PrintWriter(System.`out`)
    val n = cin.nextInt()
    val m : MutableList<P> = mutableListOf()
    for (i in 0..n-1) {
        m.add(P(i, cin.nextInt()))
    }
    val ms = m.sortedBy { it.x }

    val next = Array<Int>(n, { i -> i + 1 })
    val pre = Array<Int>(n, { i -> i - 1 })

    var ans : Long = 0L

    for (pp in ms) {
        val p = pp.idx
        val l1 = pre[p]
        val r1 = next[p]
        var l2 = pre[p]
        var r2 = next[p]
        if (next[p] < n) {
            r2 = next[next[p]]
            pre[next[p]] = pre[p]
        }
        if (pre[p] >= 0) {
            l2 = pre[pre[p]]
            next[pre[p]] = next[p]
        }
        ans += pp.x.toLong() * calc(p - l2, p - l1, r1 - p, r2 - p).toLong()
        
        
    }
    cout.println(ans)
    
    cout.flush()
}


fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun listOfString() = next().split(" ")
fun listOfInt() =listOfString().map { it.toInt() }
fun listOfLong() =listOfString().map { it.toLong() }
fun listOfDouble() =listOfString().map { it.toDouble() }