You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

土拨鼠辰辰的月赛又考砸了, 他看着一整排的教学楼和眼前的推土机, 萌生了一个邪恶的想法.

题目描述

给定两个整数$n, k$($n$表示有$n$栋教学楼, $k$表示推土机的威力), 以及一个长度为$n$的元素各不相同的数列$a$, $a_i$表示每栋教学楼的高度

每次可以选择一个长度为$k$的区间$[l, r]$, 我们可以将这个区间的教学楼推倒为$[l, r]$区间的最小值.

问最少多少次操作可以使得所有的教学楼高度都相同?

格式

输入格式

第一行两个整数$n, k$,

第二行为数列$a$

输出格式

输出一个整数, 表示最少多少次就可以推平整个学校.

样例

4 3
2 3 1 4

2

样例1解释

第一次可以选择[1, 3]区间, 教学楼高度变为{1, 1, 1, 4}

第二次可以选择[2, 4]区间, 教学楼高度变为{1, 1, 1, 1}

3 3
1 2 3

1

8 3
7 3 1 8 4 6 2 5

4

数据范围

$2 <= k <= n <= 100000$

$1 <= a_i <= n$