N=gets.to_i
ps=gets.split.map(&:to_i).unshift(nil)
ps_idx=Array.new(N+1)
ps.each_with_index do |o,i|
    next if i==0
    ps_idx[o]=i
end

checked=[0,ps_idx[N],N+1]
ans=0
(1..N-1).to_a.reverse.each do |e|
    next_idx=checked.bsearch_index{|x|ps_idx[e]<x}
    checked.insert(next_idx,ps_idx[e])
    if checked[next_idx+1]==N+1
        r=0
    else
        r=e*(checked[next_idx+2]-checked[next_idx+1])*(checked[next_idx]-checked[next_idx-1])
    end
    if checked[next_idx-1]==0
        l=0
    else
        l=e*(checked[next_idx-1]-checked[next_idx-2])*(checked[next_idx+1]-checked[next_idx])
    end
    ans+=r+l
end
p ans
