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 = list(map(int, input().split()))
  
  r = list(range(n))
  l = list(range(n))
  I = [-1] * (n + 1)
  
  for i, P in enumerate(p):
      I[P] = i
  # I[1~Nまでの数字] = 0,1,...
  # index を求めている
  ans = 0
  
  for N, index in enumerate(I[1:], 1):  # 1からスタート
      L = index - 1
      if L >= 0:
          L = l[L]
  
      R = index + 1
      if R < n:
          R = r[R]
  
      l[R - 1] = L
      r[L + 1] = R
      # 0 <= L , R < n
      if L >= 0:
          L2 = L - 1
          if L2 >= 0:
              L2 = l[L2]
          ans += N * (L - L2) * (R - index)
  
      if R < n:
          R2 = R + 1
          if R2 < n:
              R2 = r[R2]
          ans += N * (index - L) * (R2 - R)
  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"}]