题目描述

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

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$p$ を昇順にソートするために必要な総コストの最小値を出力せよ。

题目大意

给定一个排列， 你可以花费$A$使一个区间最左边的数跑到最右边， 或者花费$B$的代价使最右边到最左边， 求把整个序列变成升序的最少花费

3 20 30
3 1 2

20

4 20 30
4 2 3 1

50

1 10 10
1

0

4 1000000000 1000000000
4 3 2 1

3000000000

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\ \}$ の順列である。

Sample Explanation 1

$(p_1,\ p_2,\ p_3)$ を左にひとつシフトすると、$p\ =\ (1,\ 2,\ 3)$ となります。

Sample Explanation 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$ です。