Contest Duration: - (local time) (100 minutes) Back to Home
C - Minimization /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

スヌケ君は，この数列に対して次の操作を行うことができます．

• 数列のうち，連続した K 個の要素を選ぶ．その後，選んだ要素それぞれの値を，選んだ要素の中の最小値で置き換える．

スヌケ君は，上の操作を何回か繰り返すことで，この数列の要素をすべて等しくしたいです． 必要な操作の回数の最小値を求めてください． この問題の制約の下，このようなことは必ず可能であることが証明できます．

制約

• 2 \leq K \leq N \leq 100000
• A_1, A_2, ..., A_N1, 2, ..., N の並び替え

入力

N K
A_1 A_2 ... A_N


入力例 1

4 3
2 3 1 4


出力例 1

2


• 1 回目の操作では，1, 2, 3 番目の要素を選ぶ．すると，数列 A1, 1, 1, 4 になる．
• 2 回目の操作では，2, 3, 4 番目の要素を選ぶ．すると，数列 A1, 1, 1, 1 になる．

入力例 2

3 3
1 2 3


出力例 2

1


入力例 3

8 3
7 3 1 8 4 6 2 5


出力例 3

4


Score : 300 points

Problem Statement

There is a sequence of length N: A_1, A_2, ..., A_N. Initially, this sequence is a permutation of 1, 2, ..., N.

On this sequence, Snuke can perform the following operation:

• Choose K consecutive elements in the sequence. Then, replace the value of each chosen element with the minimum value among the chosen elements.

Snuke would like to make all the elements in this sequence equal by repeating the operation above some number of times. Find the minimum number of operations required. It can be proved that, Under the constraints of this problem, this objective is always achievable.

Constraints

• 2 \leq K \leq N \leq 100000
• A_1, A_2, ..., A_N is a permutation of 1, 2, ..., N.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 ... A_N


Output

Print the minimum number of operations required.

Sample Input 1

4 3
2 3 1 4


Sample Output 1

2


One optimal strategy is as follows:

• In the first operation, choose the first, second and third elements. The sequence A becomes 1, 1, 1, 4.

• In the second operation, choose the second, third and fourth elements. The sequence A becomes 1, 1, 1, 1.

Sample Input 2

3 3
1 2 3


Sample Output 2

1


Sample Input 3

8 3
7 3 1 8 4 6 2 5


Sample Output 3

4