Last Sunday, B21 still cannot escape from the haunting memory of "_Gate D_" in Hanoi - Amsterdam High School. He felt lost between a mob of strangers, and he was worried about his students, stuck inside the horrifyingly terrible lab of this school.
Even at night, he still had bad dreams about that day. He stuck in a one-dimensional array of integers with absolutely no sign of people. Around him, the "_ghosts_" of Lowie and Seo still fly around, whisper to his ears some crap like: "_Hanoi-Ams is better than NH High School_", or "_Our students can still outperform with 1 Gb of Random Access Memory computers_", etc. .
The array is one-dimensional, so B21 can move forward or backward (a.k.a. left or right in some other manner). From position $i$, he can move forward to position $i + 1$ or backward to $i -1$ if he is able to. Luckily, he didn't forget to dream that he get a superpower of some kind. This time: he can teleport! B21 can teleport from $i$ to $j$ only if the number written on position $i$ is equal to the number written on position $j$.
Each move forward takes B21 $R$ unit(s) of energy. Each move backward takes $L$ unit(s). And if he uses teleport, it will take him $C$ unit(s) of energy.
He want to get back to his dear Nguyen Hue High School to get more superpowers to rescue his students. Gate D (starting point) is located at position $u$ on the array, and his school (destination) is located at position $v$ on the array. What is the least amount of energy does it take for B21 to reach his destination?
First line: four integers $N$ ($2 <= N <= 10^5$) - size of the array, $L$, $R$ and $C$ ($1 <= L, R, C <= 10^9$) - cost of energy for each kind of movement.
Second line: two integers: $u$ and $v$ ($1 <= u, v <= N$) - the position of Gate D, and the position of NH High School.
Third line: $N$ integers: $A_1, A_2,..., A_N$ - elements of the array. All elements in the array is in range $[ 1, 10^9 ]$
The only line contains a single integer: the minimum energy needed to reach the destination.
In the first example, B21 moves forward and then teleports to position $5$. The total units of energy are $2 + 3 = 5$.
In the second example, B21 moves backward and then teleports to position $5$. The total units of energy are $1 + 3 = 4$.
## Input
First line: four integers $N$ ($2 <= N <= 10^5$) - size of the array, $L$, $R$ and $C$ ($1 <= L, R, C <= 10^9$) - cost of energy for each kind of movement.Second line: two integers: $u$ and $v$ ($1 <= u, v <= N$) - the position of Gate D, and the position of NH High School.Third line: $N$ integers: $A_1, A_2,..., A_N$ - elements of the array. All elements in the array is in range $[ 1, 10^9 ]$
## Output
The only line contains a single integer: the minimum energy needed to reach the destination.
[samples]
## Note
In the first example, B21 moves forward and then teleports to position $5$. The total units of energy are $2 + 3 = 5$.In the second example, B21 moves backward and then teleports to position $5$. The total units of energy are $1 + 3 = 4$.
**Definitions**
Let $ N \in \mathbb{Z} $ be the size of the array.
Let $ L, R, C \in \mathbb{Z}^+ $ be the energy costs for backward move, forward move, and teleport, respectively.
Let $ u, v \in \{1, \dots, N\} $ be the start and destination positions.
Let $ A = (A_1, A_2, \dots, A_N) $ be the array of integers, where $ A_i \in [1, 10^9] $.
Let $ G = (V, E) $ be a graph where:
- $ V = \{1, 2, \dots, N\} $ (positions in the array).
- For each $ i \in \{1, \dots, N-1\} $, there is an edge $ (i, i+1) $ with weight $ R $.
- For each $ i \in \{2, \dots, N\} $, there is an edge $ (i, i-1) $ with weight $ L $.
- For each pair $ (i, j) $ with $ i \ne j $ and $ A_i = A_j $, there is an edge $ (i, j) $ with weight $ C $.
**Constraints**
1. $ 2 \le N \le 10^5 $
2. $ 1 \le L, R, C \le 10^9 $
3. $ 1 \le u, v \le N $
4. $ 1 \le A_i \le 10^9 $ for all $ i \in \{1, \dots, N\} $
**Objective**
Compute the shortest path from node $ u $ to node $ v $ in graph $ G $, using edge weights as defined above. Output the minimum total energy required.