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 翻译