题目描述

现给你一个长度为 $n$ 的序列 $a$，你可以从中选择一个长度为 $x$ 的区间 $[l,r]$，然后将区间内的元素全部改为 $\min\{a_i\}$ 其中 $l \le i \le r$，问最少操作多少次可以使得区间内所有元素相同。

输入格式

第一行，两个整数，分别是 $n$ 和 $k$，题意见题目描述中。

第二行，$n$ 个整数，表示序列 $a$。

输出格式

一行一个整数，表示使得区间内所有元素相同的最少操作次数。

样例输入输出

5 3
3 9 4 5 6

2

10 4
15 13 5 2 4 9 10 7 3 8

3

说明/提示

【样例解释 #1】

第一次选择区间 $[1,3]$，区间变为 ${3,3,3,5,6}$。

第二次选择区间 $[3,5]$，区间变为 ${3,3,3,3,3}$。

【样例解释 #2】

第一次选择区间 $[1,4]$，区间变为 ${2,2,2,2,4,9,10,7,3,8}$。

第二次选择区间 $[4,7]$，区间变为 ${2,2,2,2,2,2,2,7,3,8}$。

第三次选择区间 $[7,10]$，区间变为 ${2,2,2,2,2,2,2,2,2,2}$。

对于 $40\% 的数据$，满足 $1 \le k < n \le 10^3$。

对于 $100\% 的数据$，满足 $1 \le k < n \le 3 \times 10^5$，$1 \le a_i \le 10^9$。