CF1810C.Make It Permutation

You have an integer array $a$ of length $n$. There are two kinds of operations you can make.

• Remove an integer from $a$. This operation costs $c$.
• Insert an arbitrary positive integer $x$ to any position of $a$ (to the front, to the back, or between any two consecutive elements). This operation costs $d$.

You want to make the final array a permutation of any positive length. Please output the minimum cost of doing that. Note that you can make the array empty during the operations, but the final array must contain at least one integer.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

你有一个长度为 $n$ 的整数数组 $a$。你可以执行以下两种操作：

• 从 $a$ 中删除一个整数，该操作花费 $c$；
• 在 $a$ 的任意位置（开头、结尾或任意两个相邻元素之间）插入一个任意的正整数 $x$，该操作花费 $d$。

你的目标是使最终数组成为某个正整数长度的排列。请输出实现该目标的最小总花费。注意：在操作过程中数组可以为空，但最终数组必须至少包含一个整数。

长度为 $n$ 的排列是指由 $1$ 到 $n$ 这 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数组中 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

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

The first line of each test case contains three integers $n$, $c$, $d$ ($1 \le n \le 10^5$, $1 \le c,d \le 10^9$).

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$ ($1 \le a_{i} \le 10^9$).

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$c$、$d$（$1 \le n \le 10^5$，$1 \le c,d \le 10^9$）。

每个测试用例的第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$（$1 \le a_{i} \le 10^9$）。

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

For each test case, output in one line the minimum cost to make the final array a permutation.

对于每个测试用例，在一行中输出使最终数组成为排列的最小代价。

In the first test case, the array is already a permutation, so there's no need for operations.

In the second test case, we can remove numbers $5$, $6$ to get the permutation $[1,2,3]$ in cost $2$. Note that we can also get a permutation by inserting a number $4$, but it costs $5$.

In the third test case, we can just remove all the numbers except for the first number $1$. It costs $8$, and the final array is $[1]$, which is a permutation of length $1$.

In the fourth test case, we can remove all the numbers except for $2$, and insert a number $1$ to the first position. It costs $4+10=14$, and the final array is $[1,2]$, which is a permutation of length $2$.

在第一个测试用例中，数组本身已经是一个排列，因此无需进行任何操作。

在第二个测试用例中，我们可以删除数字 $5$ 和 $6$，从而以代价 $2$ 得到排列 $[1,2,3]$。注意，我们也可以通过插入数字 $4$ 来得到一个排列，但其代价为 $5$。

在第三个测试用例中，我们只需保留第一个数字 $1$，删除其余所有数字。其代价为 $8$，最终数组为 $[1]$，这是一个长度为 $1$ 的排列。

在第四个测试用例中，我们可以删除除 $2$ 以外的所有数字，并在首位插入数字 $1$。其代价为 $4+10=14$，最终数组为 $[1,2]$，这是一个长度为 $2$ 的排列。