У вас есть массив целых чисел \(a\) длины \(n\). Вы можете выполнять два вида операций.
- Удалить целое число из \(a\). Эта операция стоит \(c\).
- Вставить произвольное натуральное число \(x\) в любую позицию \(a\) (в начало, в конец или между любыми двумя соседними элементами). Эта операция стоит \(d\).
Вы хотите сделать конечный массив перестановкой любой положительной длины. Пожалуйста, выведите минимальную стоимость, чтобы сделать из массива перестановку. Обратите внимание, что вы можете сделать массив пустым во время операций, но окончательный массив должен содержать хотя бы одно целое число.
Перестановкой длины \(n\) называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — это перестановка, но \([1,2,2]\) не является перестановкой (\(2\) встречается в массиве дважды), также как и \([1,3,4]\) не является перестановкой (\(n=3\), но в массиве есть элемент равный \(4\)).
Выходные данные
Для каждого набора входных данных выведите минимальную стоимость, которую нужно потратить, чтобы сделать из массива перестановку.
Примечание
В первом наборе входных данных массив уже является перестановкой, поэтому операции не нужны.
Во втором наборе входных данных мы можем удалить числа \(5\), \(6\) и получить перестановку \([1,2,3]\). Стоимость таких операций будет равна \(2\). Обратите внимание, что мы также можем получить перестановку, вставив число \(4\), но это стоит \(5\).
В третьем наборе входных данных мы можем просто удалить все числа, кроме первой \(1\). Это стоит \(8\), а окончательный массив \([1]\) представляет собой перестановку длины \(1\).
В четвертом наборе входных данных мы можем удалить все числа, кроме \(2\), и вставить одно число \(1\) на первую позицию. Это стоит \(4+10=14\), а окончательный массив \([1,2]\) представляет собой перестановку длины \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|