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: from collections import Counter
  from heapq import heappush, heappop
  
  
  def solve(n, sss):
      keys = [-1] + sorted(sss.keys())
      m = keys.pop()
      if sss[m] != 1:
          return False
      k = keys[-1]
      q = [(-n, -m)]
      while k != -1:
          r, s = heappop(q)
          r = -r
          s = -s
          if r == 0:
              continue
          if k >= s:
              tmp = set()
              while q:
                  tmp.add((-r, -s))
                  r, s = heappop(q)
                  r, s = -r, -s
                  if k < s:
                      for item in tmp:
                          heappush(q, item)
                      break
              else:
                  return False
          heappush(q, (-(r - 1), -k))
          heappush(q, (-(r - 1), -s))
          sss[k] -= 1
          if sss[k] == 0:
              keys.pop()
              k = keys[-1]
          # print(s, r, q, keys, sss)
      return True
  
  
  n = int(input())
  sss = Counter(map(int, input().split()))
  print("Yes" if solve(n, sss) else "No")
  
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"}]