module IntSet = Set.Make (struct
  type t = int
  let compare = compare
end)

let () = Scanf.scanf "%d\n" @@ fun n ->
  let ps = Array.make n 0 in
  for i = 0 to n - 1 do
    Scanf.scanf "%d " @@ fun p ->
      ps.(p - 1) <- i
  done;
  let acc = Array.make n IntSet.empty in
  for i = n - 2 downto 0 do
    acc.(i) <- IntSet.add ps.(i + 1) acc.(i + 1)
  done;
  Printf.printf "%d\n" @@
  Array.fold_left ( + ) 0 @@ 
  Array.init n @@ fun p ->
    let ls, false, rs = IntSet.split ps.(p) acc.(p) in
    let l1, l2 = 
      match IntSet.max_elt ls with
      | exception Not_found -> -1, -1
      | l2 ->
          ( try IntSet.max_elt (IntSet.remove l2 ls)
            with Not_found -> -1 ),
          l2
    and r1, r2 =
      match IntSet.min_elt rs with
      | exception Not_found -> n, n
      | r1 ->
          r1,
          ( try IntSet.min_elt (IntSet.remove r1 rs)
      with Not_found -> n ) in
    (p + 1) * 
    ((r1 - ps.(p)) * (l2 - l1) + (ps.(p) - l2) * (r2 - r1))
