题目描述

给定一个 $\{ 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

输入

3 20 30
3 1 2

输出

20

样例 2

输入

4 20 30
4 2 3 1

输出

50

样例 3

输入

1 10 10
1

输出

0

样例 4

输入

4 1000000000 1000000000
4 3 2 1

输出

3000000000

样例 5

输入

9 40 50
5 3 4 7 6 1 2 9 8

输出

220

说明/提示

限制条件

• 所有输入均为整数。
• $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 翻译