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: import heapq
  from collections import defaultdict
  
  N = int(input())
  P = list(map(int, input().split()))
  
  d_r = defaultdict(lambda: N + 1)
  h_r = []
  d_r2 = defaultdict(lambda: N + 1)
  h_r2 = []
  for i in range(N):
      p = P[i]
      while h_r2:
          q = heapq.heappop(h_r2)
          if q < p:
              d_r2[q] = p
          else:
              heapq.heappush(h_r2, q)
              break
      while h_r:
          q = heapq.heappop(h_r)
          if q < p:
              d_r[q] = p
              heapq.heappush(h_r2, q)
          else:
              heapq.heappush(h_r, q)
              break
      heapq.heappush(h_r, p)
  
  
  d_l = defaultdict(lambda: 0)
  h_l = []
  d_l2 = defaultdict(lambda: 0)
  h_l2 = []
  for i in range(N - 1, -1, -1):
      p = P[i]
      while h_l2:
          q = heapq.heappop(h_l2)
          if q < p:
              d_l2[q] = p
          else:
              heapq.heappush(h_l2, q)
              break
      while h_l:
          q = heapq.heappop(h_l)
          if q < p:
              d_l[q] = p
              heapq.heappush(h_l2, q)
          else:
              heapq.heappush(h_l, q)
              break
      heapq.heappush(h_l, p)
  
  d = {}
  for i in range(N):
      d[P[i]] = i
  d[N + 1] = N
  d[0] = -1
  ans = 0
  for i in range(N):
      x = d[d_l2[P[i]]]
      y = d[d_l[P[i]]]
      z = d[d_r[P[i]]]
      w = d[d_r2[P[i]]]
      ans += P[i] * ((y - x) * (z - i) + (w - z) * (i - y))
  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"}]