/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
長さ N の数列 A_1, A_2, ..., A_N があります．最初，この数列の要素は 1, 2, ..., N を並び替えたものになっています．
スヌケ君は，この数列に対して次の操作を行うことができます．
- 数列のうち，連続した K 個の要素を選ぶ．その後，選んだ要素それぞれの値を，選んだ要素の中の最小値で置き換える．
スヌケ君は，上の操作を何回か繰り返すことで，この数列の要素をすべて等しくしたいです． 必要な操作の回数の最小値を求めてください． この問題の制約の下，このようなことは必ず可能であることが証明できます．
制約
- 2 \leq K \leq N \leq 100000
- A_1, A_2, ..., A_N は 1, 2, ..., N の並び替え
入力
入力は以下の形式で標準入力から与えられる．
N K A_1 A_2 ... A_N
出力
必要な操作の回数の最小値を出力せよ．
入力例 1
4 3 2 3 1 4
出力例 1
2
例えば，次のようにするとよいです：
- 1 回目の操作では，1, 2, 3 番目の要素を選ぶ．すると，数列 A は 1, 1, 1, 4 になる．
- 2 回目の操作では，2, 3, 4 番目の要素を選ぶ．すると，数列 A は 1, 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