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: # -*- coding: utf-8 -*-
  import sys
  import bisect
  from collections import deque
  
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  write = sys.stdout.write
  # template
  
  
  def solve():
      n = int(readline())
      p = tuple(map(int, readline().split()))
      # print(p)
      idx = [0] * (n)
      for i in range(n):
          idx[p[i] - 1] = i
      perm = deque([-1, idx[-1], n])
      # print(perm)
      count = 0
      for i in range(n - 2, -1, -1):
          id = bisect.bisect_left(perm, idx[i])
          if id != 1:
              count += (i + 1) * ((perm[id - 1] - perm[id - 2]) * (perm[id] - idx[i]))
          if id != n - i:
              count += (i + 1) * ((perm[id + 1] - perm[id]) * (idx[i] - perm[id - 1]))
          perm.insert(id, idx[i])
      print(count)
      return
  
  
  if __name__ == "__main__":
      solve()
  
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"}]