У вас есть массив целых чисел $$$a$$$ длины $$$n$$$. Вы можете выполнять два вида операций.
Вы хотите сделать конечный массив перестановкой любой положительной длины. Пожалуйста, выведите минимальную стоимость, чтобы сделать из массива перестановку. Обратите внимание, что вы можете сделать массив пустым во время операций, но окончательный массив должен содержать хотя бы одно целое число.
Перестановкой длины $$$n$$$ называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — это перестановка, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается в массиве дважды), также как и $$$[1,3,4]$$$ не является перестановкой ($$$n=3$$$, но в массиве есть элемент равный $$$4$$$).
Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$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$$$.
Для каждого набора входных данных выведите минимальную стоимость, которую нужно потратить, чтобы сделать из массива перестановку.
83 3 31 2 35 1 51 2 3 5 65 2 31 1 1 3 35 1 102 4 6 8 106 2 87 3 5 4 4 84 10 11 2 6 74 3 32 5 8 72 1000000000 11000000000 1
0 2 8 14 20 3 12 999999998
В первом наборе входных данных массив уже является перестановкой, поэтому операции не нужны.
Во втором наборе входных данных мы можем удалить числа $$$5$$$, $$$6$$$ и получить перестановку $$$[1,2,3]$$$. Стоимость таких операций будет равна $$$2$$$. Обратите внимание, что мы также можем получить перестановку, вставив число $$$4$$$, но это стоит $$$5$$$.
В третьем наборе входных данных мы можем просто удалить все числа, кроме первой $$$1$$$. Это стоит $$$8$$$, а окончательный массив $$$[1]$$$ представляет собой перестановку длины $$$1$$$.
В четвертом наборе входных данных мы можем удалить все числа, кроме $$$2$$$, и вставить одно число $$$1$$$ на первую позицию. Это стоит $$$4+10=14$$$, а окончательный массив $$$[1,2]$$$ представляет собой перестановку длины $$$2$$$.
Название |
---|