B. Maracas
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The most classic instrument in Mexican music is the maraca, which is made up of a handle and a ball on top containing seeds and it functions as a type of rattle. As everyone knows, the use of pairs of maracas is mandatory!

You have just arrived in Mexico and will participate in a maraca circle with exactly $$$N$$$ people. At the $$$i$$$-th position of the circle, there is a number of maracas $$$m_i$$$. Your task is to redistribute the maracas so that each position has an even number of maracas to be used; after all, there cannot be a maraca without its pair. Since the circle is really big, you can only take maracas from a position and move them to the position immediately to the left or right.

The time it takes to carry a maraca from one position to another is directly proportional to the number of maracas being carried, because the greater the quantity, the heavier the weight. The time to carry a maraca to the left is $$$A$$$ seconds, and to the right is $$$B$$$ seconds. Additionally, if you're not carrying any maracas, you can move very quickly between positions (in zero seconds).

Since everyone wants to start making music as soon as possible, your goal is to determine the minimum time needed to complete this task. If it's not possible to achieve the task, you should print $$$-1$$$.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$).

The second line contains $$$N$$$ integers $$$1 \leq m_i \leq 10^9, \, i = 1,\ldots, N$$$. Note that the list of quantities of maracas is circular, that is, position $$$i$$$ is adjacent to $$$i+1$$$ and position $$$N$$$ is adjacent to position 1.

The third line contains two integers $$$A$$$ and $$$B$$$. $$$1 \leq A, B \leq 10^9$$$

Output

Print a single integer: the minimum time if possible or -1.

Examples
Input
11
2 3 4 2 3 3 1 1 9 6 10
1 9
Output
5
Input
6
1 1 1 1 1 3
4 10
Output
12