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 numpy as np
  
  N = int(input())
  P = np.array(input().split(), dtype=np.int64)
  
  A = np.zeros((N - 1, N - 1))
  B = np.zeros((N - 1, N - 1))
  
  for i in range(N - 1):
      A[i, i] = min(P[i], P[i + 1])
      B[i, i] = max(P[i], P[i + 1])
  
  for i in np.arange(N - 2)[::-1]:
      for j in np.arange(i + 1, N - 1):
          if A[i, j - 1] == A[i + 1, j]:
              if B[i, j - 1] == B[i + 1, j]:
                  A[i, j] = A[i + 1, j]
                  B[i, j] = B[i + 1, j]
              else:
                  A[i, j] = min(B[i, j - 1], B[i + 1, j])
                  B[i, j] = max(B[i, j - 1], B[i + 1, j])
  
          elif B[i, j - 1] == B[i + 1, j]:
              A[i, j] = max(A[i, j - 1], A[i + 1, j])
              B[i, j] = B[i, j - 1]
  
          elif B[i, j - 1] == A[i + 1, j]:
              A[i, j] = A[i + 1, j]
              B[i, j] = B[i + 1, j]
  
          else:
              A[i, j] = A[i, j - 1]
              B[i, j] = B[i, j - 1]
  
  print(int(np.sum(A)))
  
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"}]