/*
    Take me to church
    I'll worship like a dog at the shrine of your lies
    I'll tell you my sins and you can sharpen your knife
    Offer me that deathless death
    Good God, let me give you my life
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, L, R, A[N];
long long dp[N];
int main()
{
    scanf("%d%d%d", &n, &R, &L);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &A[i]);
    n ++; A[n] = n;
    for (int i = 1; i <= n; i ++)
    {
        int cnt = 0;
        dp[i] = LLONG_MAX;
        for (int j = i - 1; ~ j; j --)
            if (A[j] < A[i])
                dp[i] = min(dp[i], dp[j] + cnt * 1LL * L + (i - j - 1 - cnt) * 1LL * R), cnt ++;
    }
    return !printf("%lld\n", dp[n]);
}
### Prompt

Construct a cpp code solution to the problem outlined:

You are given a permutation p = (p_1, \ldots, p_N) of \\{ 1, \ldots, N \\}. You can perform the following two kinds of operations repeatedly in any order:

* Pay a cost A. Choose integers l and r (1 \leq l < r \leq N), and shift (p_l, \ldots, p_r) to the left by one. That is, replace p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r with p_{l + 1}, p_{l + 2}, \ldots, p_r, p_l, respectively.
* Pay a cost B. Choose integers l and r (1 \leq l < r \leq N), and shift (p_l, \ldots, p_r) to the right by one. That is, replace p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r with p_r, p_l, \ldots, p_{r - 2}, p_{r - 1}, respectively.



Find the minimum total cost required to sort p in ascending order.

Constraints

* All values in input are integers.
* 1 \leq N \leq 5000
* 1 \leq A, B \leq 10^9
* (p_1 \ldots, p_N) is a permutation of \\{ 1, \ldots, N \\}.

Input

Input is given from Standard Input in the following format:


N A B
p_1 \cdots p_N


Output

Print the minimum total cost required to sort p in ascending order.

Examples

Input

3 20 30
3 1 2


Output

20


Input

4 20 30
4 2 3 1


Output

50


Input

1 10 10
1


Output

0


Input

4 1000000000 1000000000
4 3 2 1


Output

3000000000


Input

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


Output

220

### Response

```cpp
/*
    Take me to church
    I'll worship like a dog at the shrine of your lies
    I'll tell you my sins and you can sharpen your knife
    Offer me that deathless death
    Good God, let me give you my life
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, L, R, A[N];
long long dp[N];
int main()
{
    scanf("%d%d%d", &n, &R, &L);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &A[i]);
    n ++; A[n] = n;
    for (int i = 1; i <= n; i ++)
    {
        int cnt = 0;
        dp[i] = LLONG_MAX;
        for (int j = i - 1; ~ j; j --)
            if (A[j] < A[i])
                dp[i] = min(dp[i], dp[j] + cnt * 1LL * L + (i - j - 1 - cnt) * 1LL * R), cnt ++;
    }
    return !printf("%lld\n", dp[n]);
}
```