output_description: Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      P_1 P_2 \ldots P_N
attempt: class BalancingTree:
      class node:
          def __init__(self, v, p):
              self.value = v
              self.pivot = p
              self.left = None
              self.right = None
  
      def __init__(self, n):
          self.N = n
          self.root = self.node(1 << n, 1 << n)
  
      def debug(self):
          def debug_info(nd_):
              return (
                  nd_.value - 1,
                  nd_.pivot - 1,
                  nd_.left.value - 1 if nd_.left else -1,
                  nd_.right.value - 1 if nd_.right else -1,
              )
  
          def debug_node(nd):
              re = []
              if nd.left:
                  re += debug_node(nd.left)
              if nd.value:
                  re.append(debug_info(nd))
              if nd.right:
                  re += debug_node(nd.right)
              return re
  
          print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])
  
      def append(self, v):  # v を追加（その時点で v はない前提）
          v += 1
          nd = self.root
          while True:
              if v == nd.value:
                  # v がすでに存在する場合に何か処理が必要ならここに書く
                  return 0
              else:
                  mi, ma = min(v, nd.value), max(v, nd.value)
                  if mi < nd.pivot:
                      nd.value = ma
                      if nd.left:
                          nd = nd.left
                          v = mi
                      else:
                          p = nd.pivot
                          nd.left = self.node(mi, p - (p & -p) // 2)
                          break
                  else:
                      nd.value = mi
                      if nd.right:
                          nd = nd.right
                          v = ma
                      else:
                          p = nd.pivot
                          nd.right = self.node(ma, p + (p & -p) // 2)
                          break
  
      def leftmost(self, nd):
          if nd.left:
              return self.leftmost(nd.left)
          return nd
  
      def rightmost(self, nd):
          if nd.right:
              return self.rightmost(nd.right)
          return nd
  
      def find_l(self, v):  # vより真に小さいやつの中での最大値（なければ-1）
          v += 1
          nd = self.root
          prev = 0
          if nd.value < v:
              prev = nd.value
          while True:
              if v <= nd.value:
                  if nd.left:
                      nd = nd.left
                  else:
                      return prev - 1
              else:
                  prev = nd.value
                  if nd.right:
                      nd = nd.right
                  else:
                      return prev - 1
  
      def find_r(self, v):  # vより真に大きいやつの中での最小値（なければRoot）
          v += 1
          nd = self.root
          prev = 0
          if nd.value > v:
              prev = nd.value
          while True:
              if v < nd.value:
                  prev = nd.value
                  if nd.left:
                      nd = nd.left
                  else:
                      if prev == 2**self.N:
                          return None
                      else:
                          return prev - 1
              else:
                  if nd.right:
                      nd = nd.right
                  else:
                      if prev == 2**self.N:
                          return None
                      else:
                          return prev - 1
  
      @property
      def find_max(self):
          return self.find_l((1 << self.N) - 1)
  
      @property
      def find_min(self):
          return self.find_r(-1)
  
      def delete(
          self, v, nd=None, prev=None
      ):  # 値がvのノードがあれば削除（なければ何もしない）
          v += 1
          if not nd:
              nd = self.root
          if not prev:
              prev = nd
          while v != nd.value:
              prev = nd
              if v <= nd.value:
                  if nd.left:
                      nd = nd.left
                  else:
                      return
              else:
                  if nd.right:
                      nd = nd.right
                  else:
                      return
          if (not nd.left) and (not nd.right):
              if nd.value < prev.value:
                  prev.left = None
              else:
                  prev.right = None
          elif not nd.left:
              if nd.value < prev.value:
                  prev.left = nd.right
              else:
                  prev.right = nd.right
          elif not nd.right:
              if nd.value < prev.value:
                  prev.left = nd.left
              else:
                  prev.right = nd.left
          else:
              nd.value = self.leftmost(nd.right).value
              self.delete(nd.value - 1, nd.right, nd)
  
      def __contains__(self, v: int) -> bool:
          return self.find_r(v - 1) == v
  
  
  def resolve():
      N = int(input())
      P = list(map(int, input().split()))
  
      A = []
      for i in range(N):
          A.append((P[i], i))
  
      A.sort(reverse=True)
  
      BT = BalancingTree(17)
      ans = 0
      for i in range(N):
          p, idx = A[i]
          BT.append(idx)
  
          l1 = BT.find_l(idx)  #
          l2 = BT.find_l(l1)
  
          r1 = BT.find_r(idx)
          if r1 is None:
              r1 = N
          r2 = BT.find_r(r1)
          if r2 is None:
              r2 = N
  
          cmb = (l1 - l2) * (r1 - idx) + (r2 - r1) * (idx - l1)
          ans += p * cmb
  
      print(ans)
  
  
  if __name__ == "__main__":
      resolve()
  
problem_description: Statement
  
  Given is a permutation P of \\{1, 2, \ldots, N\\}.
  
  For a pair (L, R) (1 \le L \lt R \le N), let X_{L, R} be the second largest
  value among P_L, P_{L+1}, \ldots, P_R.
  
  Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.
samples: [{"input": "3\n    2 3 1", "output": "5\n    \n\nX_{1, 2} = 2, X_{1, 3} = 2, and X_{2, 3} = 1, so the sum is 2 + 2 + 1 = 5.\n\n* * *"}, {"input": "5\n    1 2 3 4 5", "output": "30\n    \n\n* * *"}, {"input": "8\n    8 2 7 3 4 5 6 1", "output": "136"}]