Задача: Минимизация
Имеется последовательность длины N: A1, A2, ..., AN. Изначально эта последовательность представляет собой перестановку 1, 2, ..., N. В этой последовательности Алиса может выполнить следующую операцию:
1) выбрать K последовательных элементов в последовательности;
2) затем заменить значение каждого выбранного элемента минимальным значением среди выбранных элементов.
Алиса хочет уравнять все элементы в этой последовательности, повторяя указанную выше операцию некоторое количество раз.
Найдите минимальное количество необходимых операций.
Можно доказать, что при ограничениях этой проблемы эта цель всегда достижима.
Входные данные
В первой строке задаются два целых числа N и K (2<=K<=N<=100000). Во второй строке задается последовательность целых чисел A1, A2, ..., AN - перестановка чисел от 1 до N (каждое число в последовательности различно, 1<=Ai<=N).
Выходные данные
Выведите минимальное количество необходимых операций.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 3
2 3 1 4 |
2 |
| 2 |
3 3
1 2 3 |
1 |
| 3 |
8 3
7 3 1 8 4 6 2 5 |
4 |
Ваш ответ: