fun readList() = readLine()!!.split(" ").map(Integer::parseInt)
fun main(args:Array<String>){
  val N = readLine()!!.toInt()
  val P = readList()
  val Q = Array(N){it}
  Q.sortBy{-P[it]}
  var answer = 0L
  val maxes = sortedSetOf<Int>(-1,N)
  var L0:Int
  var L1:Int
  var R0:Int
  var R1:Int
  for(i in Q){
    L0 = -1
    L1 = -1
    R0 = N
    R1 = N
    L1=maxes.lower(i)
    if(L1!=-1)L0=maxes.lower(L1)
    R0=maxes.higher(i)
    if(R0!=N)R1=maxes.higher(R0)
    answer += P[i].toLong()*((L1-L0)*(R0-i)+(i-L1)*(R1-R0))
    maxes += i
  }
  println(answer)
}
