God's Blessing on This PermutationForces!
A Random Pebble
Дана перестановка \(p_1,p_2,\ldots,p_n\) длины \(n\) и целое положительное число \(k \le n\).
За одну операцию вы можете выбрать два целых числа \(i\) и \(j\) (\(1 \le i < j \le n\)) и поменять местами \(p_i\) и \(p_j\).
Найдите минимальное количество операций, необходимых для того, чтобы сделать сумму \(p_1 + p_2 + \ldots + p_k\) минимально возможной.
Перестановкой является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для того, чтобы сделать сумму \(p_1 + p_2 + \ldots + p_k\) минимально возможной.
Примечание
В первом наборе входных данных сумма \(p_1 + p_2 + \ldots + p_k\) изначально равна \(2\), но минимально возможное значение равно \(1\). Его можно достичь, поменяв местами \(p_1\) и \(p_3\), тогда результирующая перестановка будет равна \([1, 3, 2]\).
Во втором наборе входных данных сумма уже минимально возможная, поэтому ответ — \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 1
2 3 1
3 3
1 2 3
4 2
3 4 1 2
1 1
1
|
1
0
2
0
|