题目描述

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

• 支付代价 $A$。选择整数 $l$ 和 $r$ ($1 \leq l < r \leq N$)，将 $(p_l, \ldots, p_r)$ 向左移动一位。也就是用 $p_{l + 1}, p_{l + 2}, \ldots, p_r, p_l$ 替换 $p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r$。
• 支付代价 $B$。选择整数 $l$ 和 $r$ ($1 \leq l < r \leq N$)，将 $(p_l, \ldots, p_r)$ 向右移动一位。也就是用 $p_r, p_l, \ldots, p_{r - 2}, p_{r - 1}$ 替换 $p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r$。

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

约束条件

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

输入

输入以以下格式从标准输入给出：

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

输出

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

示例输入1

3 20 30
3 1 2

示例输出1

20

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

示例输入2

4 20 30
4 2 3 1

示例输出2

50

一种可能的操作序列如下：

• 将 $(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$。

示例输入3

1 10 10
1

示例输出3

0

示例输入4

4 1000000000 1000000000
4 3 2 1

示例输出4

3000000000

示例输入5

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

示例输出5

220