最小化

题目描述

有一个长度为 $N$ 的数列 $A_1, A_2, ..., A_N$。最初,该数列是将 $1, 2, ..., N$ 打乱顺序排列得到的一个排列。

Snuke君可以对数列进行如下操作:

• 选出数列中连续的一段共 $K$ 个元素。然后,将选出的每个元素的值都替换为所选元素中的最小值。

Snuke君希望通过重复若干次上述操作,使数列的所有元素都相等。 请求出所需操作次数的最小值。 可以证明,在此问题的约束下,这样的操作一定可行。

输入格式

输入以以下格式从标准输入给出。

$N$ $K$
$A_1$ $A_2$ $...$ $A_N$

输出格式

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

样例

4 3
2 3 1 4

2

例如,可以这样操作:

• 第 $1$ 次操作,选择第 $1, 2, 3$ 个元素。于是数列 $A$ 变为 $1, 1, 1, 4$。
• 第 $2$ 次操作,选择第 $2, 3, 4$ 个元素。于是数列 $A$ 变为 $1, 1, 1, 1$。

3 3
1 2 3

1

8 3
7 3 1 8 4 6 2 5

4

数据范围

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