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

def f(i)
  p = P[i]
  r1 = (i + 1 ... N).find{|j| P[j] > p} || N
  r2 = (r1 + 1... N).find{|j| P[j] > p} || N
  l1 = (i - 1).downto(0).find{|j| P[j] > p} || -1
  l2 = (l1 - 1).downto(0).find{|j| P[j] > p} || -1
  p*((l1 - l2)*(r1 - i) + (i - l1)*(r2 - r1))
end

puts (0 ... N).inject(0){|s, i| s + f(i)}