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: N = int(input())
  P_id = [0] * (N + 1)  # P_id[i]は順列Pに置けるiのindex, P[0]は無視
  for index, p in enumerate(map(int, input().split())):
      P_id[p] = index
  
  left_next_index = list(range(-1, N - 1)) + [
      "うんこ",
      -1,
  ]  # + [- 1]ではないことに注意, left_next_index[r1] = l1においてr1 = Nの場合があるから
  right_next_index = list(range(1, N + 1)) + [N, "うんこ"]
  
  res = 0
  for p in range(1, N):
      l1 = left_next_index[P_id[p]]
      l2 = left_next_index[l1]
      r1 = right_next_index[P_id[p]]
      r2 = right_next_index[r1]
  
      res += p * ((l1 - l2) * (r1 - P_id[p]) + (P_id[p] - l1) * (r2 - r1))
  
      left_next_index[r1] = l1
      right_next_index[l1] = r1
  
  print(res)
  
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"}]