問題文

$\\{ 1, \\ldots, N \\}$ の順列 $p = (p_1, \\ldots, p_N)$ が与えられます。 あなたは、次の 2 種類の操作を好きな順序で繰り返し行うことができます。

• コスト $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$ を昇順にソートするために必要な総コストの最小値を求めてください。

制約

• 入力はすべて整数である。
• $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