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

R = (N - 2).downto(1).each_with_object(P.dup + [0]){|i, o| o[i] = o[i, 2].max}.drop(1)
L = (1 ... N).each_with_object([0] + P.dup){|i, o| o[i] = o[i - 1, 2].max}.take(N)

def f(i)
  p = P[i]
  r1 = R[i] < p ? N : (i + 1 ... N).find{|j| P[j] > p}
  r2 = (r1 + 1... N).find{|j| P[j] > p} || N
  l1 = L[i] < p ? -1 : (i - 1).downto(0).find{|j| P[j] > p}
  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)}