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 = [int(i) for i in input().split()]
  ans = 0
  for i in range(n):  # 左端から
      if i == 0:  # 一番左なら
          if p[i] == n:
              ans += 0
          elif p[i] == n - 1:
              idx = p.index(n)
              ans += p[i] * (n - idx)
          else:
              idx = []
              for j in reversed(range(p[i] + 1, n + 1)):
                  idx.append(p.index(j))
              idx.sort()
              temp = idx[1] - idx[0]
              ans += p[i] * temp
      elif i == n - 1:  # 右端なら
          if p[i] == n:
              ans += 0
          elif p[i] == n - 1:
              idx = p.index(n)
              ans += p[i] * (idx + 1)
          else:
              idx = []
              for j in reversed(range(p[i] + 1, n + 1)):
                  idx.append(p.index(j))
              idx.sort()
              temp = idx[-1] - idx[-2]
              ans += p[i] * temp
      else:  # 真ん中なら
          if p[i] == n:
              ans += 0
          elif p[i] == n - 1:
              idx = p.index(n)
              chi = min(i, idx)
              ook = max(i, idx)
              temp = (chi + 1) * (n - ook)
              ans += p[i] * temp
          else:  # 「大」が2つ以上あるとき
              left = p[:i]
              right = p[i + 1 :]
              if max(left) < p[i]:  # 小●大
                  idx = []
                  for j in range(i + 1, n):
                      if p[j] > p[i] and (len(idx) < 2):
                          idx.append(j)
                      elif len(idx) == 2:
                          break
                      else:
                          idx = idx
                  temp = (i + 1) * (idx[1] - idx[0])
                  ans += p[i] * temp
              elif max(right) > p[i]:  # 大●小
                  idx = []
                  for j in reversed(range(i)):
                      if p[j] > p[i] and (len(idx) < 2):
                          idx.append(j)
                      elif len(idx) == 2:
                          break
                      else:
                          idx = idx
                  temp = (n - i) * (idx[0] - idx[1])
                  ans += temp * p[i]
              else:
                  idx_left = []
                  for k in reversed(range(i)):
                      if p[k] > p[i] and (len(idx_left) < 2):
                          idx_left.append(k)
                      elif len(idx_left) == 2:
                          break
                      else:
                          idx_left = idx_left
                  if len(idx_left) < 2:
                      idx_left.append(-1)
                  idx_right = []
                  for l in range(i + 1, n):
                      if p[l] > p[i] and (len(idx_right) < 2):
                          idx_right.append(l)
                      elif len(idx_right) == 2:
                          break
                      else:
                          idx_right = idx_right
                  if len(idx_right) < 2:
                      idx_right.append(n)
                  temp_left = (idx_right[0] - i) * (idx_left[0] - idx_left[1])
                  temp_right = (idx_right[1] - idx_right[0]) * (i - idx_left[0])
                  temp = temp_left + temp_right
                  ans += p[i] * temp
  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"}]