题目描述

给定一个长为 n 的序列 a，你可以进行以下两个操作：

1. 删除 a 中的任意一个数字，花费为 c。
2. 往 a 的任意位置插入一个数字，花费为 d。

求最后得到一个任意长度的排列的最小花费。

注：最终排列长度不能为 0，但操作中序列长度可以为 0。

#数据范围：$1≤n≤10^5,1≤c,d≤10^9,1≤a_i≤10^9$。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$，表示用例数量。

每组数据的第一行包含 $3$ 个整数，$n,c,d$。

每个测试用例的第二行包含 $n$ 个整数，$a_1,a_2,...,a_n$。

输出格式

8
3 3 3
1 2 3
5 1 5
1 2 3 5 6
5 2 3
1 1 1 3 3
5 1 10
2 4 6 8 10
6 2 8
7 3 5 4 4 8
4 10 1
1 2 6 7
4 3 3
2 5 8 7
2 1000000000 1
1000000000 1

0
2
8
14
20
3
12
999999998

提示

样例解释：

在第一个测试用例中，数组已经是一个排列，因此不需要作。

在第二个测试用例中，我们可以删除数字 5,6 获取排列 [1,2,3]成本为 2.请注意，我们也可以通过插入一个数字4 来获得排列，但成本为 $5$.

在第三个测试用例中，我们可以只删除除第一个数字之外的所有数字 .费用 8，最终数组为 [1]，这是长度为 $1$ 的排列。

在第四个测试用例中，删除 4,6,8,10，然后插入一个数字 1 到第一个位置。费用 4*1+10=14，最终数组为 [1,2]。