Вам дана перестановка\(^\dagger\) \(p\) длины \(n\) и положительное число \(k \le n\).
За одну операцию вы:
- Выбираете \(k\) различных элементов \(p_{i_1}, p_{i_2}, \ldots, p_{i_k}\).
- Удаляете их из массива и добавляете эти элементы в конец массива в отсортированном по возрастанию порядке.
Например, если \(p = [2,5,1,3,4]\) и \(k = 2\), и вы выберете \(5\) и \(3\) как элементы для операции, то операция будет выглядеть так: \([2, \color{red}{5}, 1, \color{red}{3}, 4] \rightarrow [2, 1, 4, \color{red}{3},\color{red}{5}]\).
Найдите минимальное число операций, которое необходимо сделать, чтобы отсортировать массив по возрастанию. Можно показать, что это всегда возможно сделать.
\(^\dagger\) Перестановкой длины \(n\) называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) встречается дважды в массиве) и \([1,3,4]\) тоже не является перестановкой (\(n=3\), но \(4\) присутствует в массиве).
Выходные данные
Для каждого набора входных данных выведите одно число — минимальное количество операций, которое необходимо сделать, чтобы отсортировать массив. Можно показать, что это всегда возможно.
Примечание
В первом наборе входных данных массив уже отсортирован.
Во втором наборе можно выбрать число \(3\) и перестановка станет отсортированной: \([\color{red}{3}, 1, 2] \rightarrow [1, 2, \color{red}{3}]\).
В третьем наборе входных данных можно выбрать \(3\) и \(4\), тогда перестановка станет отсортированной: \([1, \color{red}{3}, 2, \color{red}{4}] \rightarrow [1, 2, \color{red}{3},\color{red}{4}]\).
Можно показать, что в четвертом наборе за \(1\) операцию отсортировать массив невозможно. А за две операции можно отсортировать так: в первой операции выбрать элементы \(2\) и \(1\), а во второй выбрать \(3\) и \(4\). Тогда перестановка станет отсортированной: \([\color{red}{2}, 3, \color{red}{1}, 4] \rightarrow [\color{blue}{3}, \color{blue}{4}, \color{red}{1}, \color{red}{2}] \rightarrow [1,2, \color{blue}{3}, \color{blue}{4}]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 2
1 2 3
3 1
3 1 2
4 2
1 3 2 4
4 2
2 3 1 4
|
0
1
1
2
|