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, ans, sum = int(input()), 0, 0
  P = list(map(int, input().split()))
  first, second = P[n - 1], P[n - 1]
  first_pos, second_pos = n - 1, n - 1
  li = 0
  count = 1
  
  for i in range(n - 2, -1, -1):
      x = P[i]
      if x > first:
          second = first
          first = x
          second_pos = first_pos
          first_pos = i
          sum = li + (n - second_pos) * second
          li = 0
  
      elif second < x and x < first:
          second, second_pos = x, i
          sum = second * (n - i - 1)
          count += 1
          li += x
  
      else:
          sum += x
          count += 1
          li += x
  
      ans += sum
  
  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"}]