Имеется последовательность длины
N:
A1,
A2,
...,
AN. Изначально эта последовательность представляет собой перестановку
1,
2,
...,
N. В этой последовательности Алиса может выполнить следующую операцию:
1) выбрать
K последовательных элементов в последовательности;
2) затем заменить значение каждого выбранного элемента минимальным значением среди выбранных элементов.
Алиса хочет уравнять все элементы в этой последовательности, повторяя указанную выше операцию некоторое количество раз.
Найдите минимальное количество необходимых операций.
Можно доказать, что при ограничениях этой проблемы эта цель всегда достижима.
Входные данные
В первой строке задаются два целых числа
N и
K (2<=K<=N<=100000). Во второй строке задается последовательность целых чисел
A1,
A2,
...,
AN - перестановка чисел от 1 до N (каждое число в последовательности различно, 1<=A
i<=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 |