# Studying https://atcoder.jp/contests/abc140/submissions/7391384

N = gets.to_i
P = gets.split.map &:to_i

Pi = [nil] * N
P.each_with_index{|p, i|
	Pi[p-1] = i
}

RU = (1..N).to_a + [N, N]
LU = (-1..(N-2)).to_a + [-1, -1]

p Pi.inject(0){|sum, i|
	 l,  r = LU[i], RU[i]
	ll, rr = LU[l], RU[r]
	LU[r], RU[l] = l, r
	next sum + P[i] * ((i-l)*(rr-r) + (r-i)*(l-ll))
}
