AT_agc032_d.[AGC032D] Rotation Sort

给定一个 $ { 1, \ldots, N } $ 的排列 $ p = (p_1, \ldots, p_N) $。你可以按任意顺序重复进行以下两种操作：

• 支付代价 $ A $。任选整数 $ l $ 和 $ r $（$ 1 \leq l < r \leq N $），将 $ (p_l, \ldots, p_r) $ 整体向左移动一位。即将 $ p_l, p_{l+1}, \ldots, p_{r-1}, p_r $ 依次替换为 $ p_{l+1}, p_{l+2}, \ldots, p_r, p_l $。
• 支付代价 $ B $。任选整数 $ l $ 和 $ r $（$ 1 \leq l < r \leq N $），将 $ (p_l, \ldots, p_r) $ 整体向右移动一位。即将 $ p_l, p_{l+1}, \ldots, p_{r-1}, p_r $ 依次替换为 $ p_r, p_l, \ldots, p_{r-2}, p_{r-1} $。

请你求出将 $ p $ 升序排序所需的最小总代价。

输入以如下格式从标准输入读入：

$ N $ $ A $ $ B $ $ p_1 $ $ \cdots $ $ p_N $

输出将 $ p $ 升序排序所需的最小总代价。

限制条件

• 所有输入均为整数。
• $ 1 \leq N \leq 5000 $
• $ 1 \leq A, B \leq 10^9 $
• $ (p_1, \ldots, p_N) $ 是 $ { 1, \ldots, N } $ 的一个排列。

样例解释 1

将 $ (p_1, p_2, p_3) $ 向左移动一位后，$ p = (1, 2, 3) $。

样例解释 2

例如，可以按如下方式操作：

• 将 $ (p_1, p_2, p_3, p_4) $ 向左移动一位，此时 $ p = (2, 3, 1, 4) $。
• 将 $ (p_1, p_2, p_3) $ 向右移动一位，此时 $ p = (1, 2, 3, 4) $。
  此时总代价为 $ 20 + 30 = 50 $。

由 ChatGPT 4.1 翻译