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())
  ls = [int(s) for s in input().split()]
  count = 0
  
  
  def plus(ls):
      L = len(ls)
      if L > 1:
          val_ls = ls
          a = max(val_ls)
          i1 = ls.index(a)
          val_ls[i1] = 0
          b = max(val_ls)
          i2 = ls.index(b)
          val_ls[i1] = a
          i3 = max([i1, i2])
          i4 = min([i1, i2])
          #    print(a,b,i4,i3)
          return [(i4 + 1) * (L - i3) * b, i4, i3]
      else:
          return 0
  
  
  S = [ls]
  T = []
  ans = 0
  sign = 1
  while S != []:
      while S != []:
          Ls = S[0]
          e = plus(Ls)
          if e == 0:
              S.pop(0)
          else:
              #  print(Ls,e)
              ans += e[0] * sign
              S.pop(0)
              S.append(Ls[: e[2]])
              S.append(Ls[e[1] + 1 :])
              T.append(Ls[e[1] + 1 : e[2]])
      S = T
      sign *= -1
  #  print(S,T,ans)
  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"}]