[AGC032D] Rotation Sort

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

[problemUrl]: https://atcoder.jp/contests/agc032/tasks/agc032_d $ \{\ 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 $ を昇順にソートするために必要な総コストの最小値を出力せよ。

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