C-最小化

得分: $300$ 分

问题描述

有一个长度为 $N$ 的序列: $A_1, A_2, ..., A_N$。最初，这个序列是 $1, 2, ..., N$ 的排列。

在这个序列上，Snuke可以执行以下操作：

• 选择连续的 $K$ 个元素在序列中。然后，将每个被选中元素的值替换为被选中元素的最小值。

Snuke希望通过重复上述操作使得这个序列中的所有元素都相等。找到所需的最小操作次数。可以证明，在此问题的约束条件下，这个目标总是可以达到的。

约束

• $2 \leq K \leq N \leq 100000$
• $A_1, A_2, ..., A_N$ 是 $1, 2, ..., N$ 的排列。

输入

输入数据从标准输入给出，格式如下:

$N$ $K$

$A_1$ $A_2$ $...$ $A_N$

输出

输出所需的最小操作次数。

4 3
2 3 1 4

2

其中一种最佳策略如下：

• 在第一次操作中，选择前三个元素。序列 $A$ 变为 $1, 1, 1, 4$。

• 在第二次操作中，选择后三个元素。序列 $A$ 变为 $1, 1, 1, 1$。

3 3
1 2 3

1

8 3
7 3 1 8 4 6 2 5

4