该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
现给你一个长度为 n 的序列 a,你可以从中选择一个长度为 x 的区间 [l,r],然后将区间内的元素全部改为 min{ai} 其中 l≤i≤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≤k<n≤103。
对于 100%的数据,满足 1≤k<n≤3×105,1≤ai≤109。