A. Levi Is Sad
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a faraway school early in the morning. The school manager asked the $$$n$$$ students to line up in a row at the top of the wall.

They lined up one after the other according to the time of their arrival. Each student has a length of $$$h_i$$$ centimeters.

Meanwhile, there was a student named Levi who was angry because he was the shortest among the students. When he was asked about the reason for his anger, it became clear that he did not want to be the shortest person between the person in front of him and the person behind him.

The manager decided to make everyone happy without changing their places, by removing stones below any student, or even by adding stones under any student. Each stone is only one centimeter long, so when a stone is added, the person becomes one centimeter taller, and vice versa when removed.

Adding a stone anywhere costs $$$x$$$ energy units, and removing a stone anywhere costs $$$y$$$ energy units.

You can consider the length of the wall to be infinite and you can remove any amount of stones you want.

You can consider that the first and last students are always happy.

You need to find the minimum cost to make all students happy.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n,x,y$$$ $$$(1 \le n \le 10^5, 0 \le x,y \le 10^9)$$$ — the number of students, the cost of adding a stone, and the cost of removing a stone, respectively.

The second line of each test case contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ $$$(0 \le h_i \le 5 \cdot 10^3)$$$ — the length of each student.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum cost to make all students happy.

Example
Input
2
4 5 5
1 6 2 5
6 2 4
5 4 5 5 4 6
Output
15
4
Note

In the first test case, the student standing in place $$$3$$$ is sad because he is shorter than the one in front of him in place $$$4$$$ and the one behind him in place $$$2$$$, to make him happy we will remove $$$3$$$ stones from the person in front of him. Thus, the lengths become as follows $$$h=[1,6,2,2]$$$ and everyone becomes happy.

In the second test case, students $$$2$$$ and $$$5$$$ are sad, so to make them happy at the lowest cost, we will add a stone below each one of them, then the lengths become as follows $$$h=[5,5,5,5,5,6]$$$.