#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']

require 'prime'

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def sum(a) a.inject(:+) end

def big(a,b) return (a>b)? a:b end

def small(a,b) return (a<b)? a:b end

def ins(bit,ind,pl)
  while ind < bit.size
    bit[ind] += pl
    ind += ind & -ind
  end
end

def pop(bit,c)
  pl = bit.size - 1
  ind = pl
  pl >>= 1
  return false if(bit[-1] < c)
  while pl > 0
    return false if ind >= bit.size
    if(bit[ind] < c)
      c -= bit[ind]
      ind += pl
    else
      ind -= pl
    end
    pl >>= 1
  end
  if(bit[ind] < c)
    ind += 1
  end
  return ind
end


def b_sum (bit, ind)
  sum = 0
  while ind > 0
    sum += bit[ind]
    ind -= ind & -ind
  end
  return sum
end

bit = na(2**20+1)
n = inp[0]
pt = inp
d=[]
pt.size.times do |i|
  d << [i+2,pt[i]]
end
d.sort_by!{|u|u[1]*-1}
ins(bit,1,2)
ins(bit,n+2,2)
ans = 0
d.each.with_index do |a,i|
  ins(bit,a[0],1)
  my = b_sum(bit, a[0])
  x1 = pop(bit,my-2)
  x2 = pop(bit,my-1)
  x3 = pop(bit,my+1)
  x4 = pop(bit,my+2)
  ans += ((x2-x1)*(x3-a[0]) + (x4-x3)*(a[0] -x2) )* a[1]
end
p ans