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 BIT:
      def __init__(self, n):
          self.n = n
          self.data = [0] * (n + 1)
  
      def ope(self, x, y):
          return x + y
  
      def update(self, i, v):
          while i <= self.n:
              self.data[i] = self.ope(self.data[i], v)
              i += i & -i
  
      def query(self, i):
          ret = 0
          while 0 < i:
              ret = self.ope(self.data[i], ret)
              i &= i - 1
          return ret
  
      def lowerBound(self, w):
          if w <= 0:
              return 0
          x, k = 0, 2 ** self.n.bit_length()
          while k:
              if x + k <= self.n and self.data[x + k] < w:
                  w -= self.data[x + k]
                  x += k
              k >>= 1
          return x + 1
  
  
  n = int(input())
  p = list(map(int, input().split()))
  pos = [0] * n
  for i, pi in enumerate(p):
      pos[pi - 1] = i
  
  bit1 = BIT(n)
  bit2 = BIT(n)
  ans = 0
  for pi in range(n, 0, -1):
      i = pos[pi - 1]
      cur = bit1.query(i + 1)
      if cur == 0:
          left_0 = i + 1
          left_1 = 0
      else:
          tmp = bit1.lowerBound(cur)
          tmp2 = bit1.lowerBound(cur - 1)
          left_0 = i + 1 - tmp
          left_1 = tmp - tmp2
      # 更新
      bit1.update(i + 1, 1)
      j = n - i - 1
      cur = bit2.query(j + 1)
      if cur == 0:
          right_0 = j + 1
          right_1 = 0
      else:
          tmp = bit2.lowerBound(cur)
          tmp2 = bit2.lowerBound(cur - 1)
          right_0 = j + 1 - tmp
          right_1 = tmp - tmp2
      # 更新
      bit2.update(j + 1, 1)
      ans += pi * (left_0 * right_1 + left_1 * right_0)
  
  print(ans)
  
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"}]