output_description: Print the minimum total cost required to sort p in ascending order.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N A B
      p_1 \cdots p_N
attempt: n, a, b = 5000, 10000000, 10000000
  p = list(range(n, 0, -1))
  q = [0] * n
  for i, x in enumerate(p):
      q[x - 1] = i
  dp = [[0] * (n + 1) for _ in range(n + 1)]
  mi = [[n] * (n + 1) for _ in range(n + 1)]
  ma = [[0] * (n + 1) for _ in range(n + 1)]
  for i in range(n + 1):
      for j in range(i + 1, n + 1):
          mi[i][j] = min(mi[i][j - 1], q[j - 1])
          ma[i][j] = max(ma[i][j - 1], q[j - 1])
  for i in range(1, n + 1):
      for j in range(i + 1):
          k = i - j
          s, t = 1, 1
          if j > 0 and j == p[mi[j - 1][n - k]]:
              s = 0
          if k > 0 and n - k + 1 == p[ma[j][n - k + 1]]:
              t = 0
          if j == 0:
              dp[j][k] = dp[j][k - 1] + a * t
          elif k == 0:
              dp[j][k] = dp[j - 1][k] + b * s
          else:
              dp[j][k] = min(dp[j - 1][k] + b * s, dp[j][k - 1] + a * t)
  ans = float("inf")
  for i in range(n + 1):
      ans = min(ans, dp[i][n - i])
  print(ans)
  
problem_description: Statement
  
  You are given a permutation p = (p_1, \ldots, p_N) of \\{ 1, \ldots, N \\}.
  You can perform the following two kinds of operations repeatedly in any order:
  
    * Pay a cost A. Choose integers l and r (1 \leq l < r \leq N), and shift (p_l, \ldots, p_r) to the left by one. That is, replace p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r with p_{l + 1}, p_{l + 2}, \ldots, p_r, p_l, respectively.
    * Pay a cost B. Choose integers l and r (1 \leq l < r \leq N), and shift (p_l, \ldots, p_r) to the right by one. That is, replace p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r with p_r, p_l, \ldots, p_{r - 2}, p_{r - 1}, respectively.
  
  Find the minimum total cost required to sort p in ascending order.
samples: [{"input": "3 20 30\n    3 1 2", "output": "20\n    \n\nShifting (p_1, p_2, p_3) to the left by one results in p = (1, 2, 3).\n\n* * *"}, {"input": "4 20 30\n    4 2 3 1", "output": "50\n    \n\nOne possible sequence of operations is as follows:\n\n  * Shift (p_1, p_2, p_3, p_4) to the left by one. Now we have p = (2, 3, 1, 4).\n  * Shift (p_1, p_2, p_3) to the right by one. Now we have p = (1, 2, 3, 4).\n\nHere, the total cost is 20 + 30 = 50.\n\n* * *"}, {"input": "1 10 10\n    1", "output": "0\n    \n\n* * *"}, {"input": "4 1000000000 1000000000\n    4 3 2 1", "output": "3000000000\n    \n\n* * *"}, {"input": "9 40 50\n    5 3 4 7 6 1 2 9 8", "output": "220"}]