CF1491B.Minimal Cost

There is a graph of $n$ rows and $10^6 + 2$ columns, where rows are numbered from $1$ to $n$ and columns from $0$ to $10^6 + 1$:

Let's denote the node in the row $i$ and column $j$ by $(i, j)$.

Initially for each $i$ the $i$-th row has exactly one obstacle — at node $(i, a_i)$. You want to move some obstacles so that you can reach node $(n, 10^6+1)$ from node $(1, 0)$ by moving through edges of this graph (you can't pass through obstacles). Moving one obstacle to an adjacent by edge free node costs $u$ or $v$ coins, as below:

• If there is an obstacle in the node $(i, j)$, you can use $u$ coins to move it to $(i-1, j)$ or $(i+1, j)$, if such node exists and if there is no obstacle in that node currently.
• If there is an obstacle in the node $(i, j)$, you can use $v$ coins to move it to $(i, j-1)$ or $(i, j+1)$, if such node exists and if there is no obstacle in that node currently.
• Note that you can't move obstacles outside the grid. For example, you can't move an obstacle from $(1,1)$ to $(0,1)$.

Refer to the picture above for a better understanding.

Now you need to calculate the minimal number of coins you need to spend to be able to reach node $(n, 10^6+1)$ from node $(1, 0)$ by moving through edges of this graph without passing through obstacles.

有一个 $n$ 行、$10^6 + 2$ 列的图，行编号为 $1$ 至 $n$，列编号为 $0$ 至 $10^6 + 1$：

我们用 $(i, j)$ 表示第 $i$ 行、第 $j$ 列的节点。

初始时，对每个 $i$，第 $i$ 行恰好有一个障碍物，位于节点 $(i, a_i)$。你需要移动一些障碍物，使得能够从节点 $(1, 0)$ 出发，沿图的边到达节点 $(n, 10^6+1)$（路径上不能经过任何障碍物）。将一个障碍物移动到一个相邻的、当前为空闲的节点所需花费为 $u$ 或 $v$ 枚金币，具体规则如下：

• 若节点 $(i, j)$ 上存在障碍物，则可花费 $u$ 枚金币将其移至 $(i-1, j)$ 或 $(i+1, j)$（若该目标节点在图内且当前为空闲）；
• 若节点 $(i, j)$ 上存在障碍物，则可花费 $v$ 枚金币将其移至 $(i, j-1)$ 或 $(i, j+1)$（若该目标节点在图内且当前为空闲）；
• 注意：障碍物不可移出网格边界。例如，不可将位于 $(1,1)$ 的障碍物移至 $(0,1)$。

请参考上方图片以获得更直观的理解。

现在你需要计算：为使得能从节点 $(1, 0)$ 沿图的边到达节点 $(n, 10^6+1)$（路径上不经过任何障碍物），所需花费的最少金币数。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains three integers $n$, $u$ and $v$ ($2 \le n \le 100$, $1 \le u, v \le 10^9$) — the number of rows in the graph and the numbers of coins needed to move vertically and horizontally respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — where $a_i$ represents that the obstacle in the $i$-th row is in node $(i, a_i)$.

It's guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^4$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$u$ 和 $v$（$2 \le n \le 100$，$1 \le u, v \le 10^9$）—— 分别表示图中的行数，以及垂直移动和水平移动所需的金币数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）—— 其中 $a_i$ 表示第 $i$ 行中的障碍物位于节点 $(i, a_i)$ 处。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^4$。

For each test case, output a single integer — the minimal number of coins you need to spend to be able to reach node $(n, 10^6+1)$ from node $(1, 0)$ by moving through edges of this graph without passing through obstacles.

It can be shown that under the constraints of the problem there is always a way to make such a trip possible.

对于每个测试用例，输出一个整数——即：在不经过障碍物的前提下，通过图中的边从节点 $(1, 0)$ 到达节点 $(n, 10^6+1)$ 所需花费的最少硬币数。

可以证明，在本题的约束条件下，总存在一种方式使这样的行程成为可能。

In the first sample, two obstacles are at $(1, 2)$ and $(2,2)$. You can move the obstacle on $(2, 2)$ to $(2, 3)$, then to $(1, 3)$. The total cost is $u+v = 7$ coins.

In the second sample, two obstacles are at $(1, 3)$ and $(2,2)$. You can move the obstacle on $(1, 3)$ to $(2, 3)$. The cost is $u = 3$ coins.

在第一个样例中，两个障碍物位于 $(1, 2)$ 和 $(2, 2)$。你可以将位于 $(2, 2)$ 的障碍物先移动到 $(2, 3)$，再移动到 $(1, 3)$。总花费为 $u+v = 7$ 枚金币。

在第二个样例中，两个障碍物位于 $(1, 3)$ 和 $(2, 2)$。你可以将位于 $(1, 3)$ 的障碍物移动到 $(2, 3)$。花费为 $u = 3$ 枚金币。