该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

留下峰值

时间限制：$1$ 秒。内存限制：$512$ MB。

题目描述

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$ 和一个整数 $k$。

你可以保留若干位置的原值，并将其他位置的值改为 $0$，得到序列 $b$。要求每个长度恰为 $k$ 的连续区间，其最大值都保持不变，即对于所有 $1\le l\le n-k+1$，都有

求最少需要保留多少个位置。

输入格式

输入文件：peak.in。

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出文件：peak.out。

输出一行一个整数，表示最少需要保留的位置数量。

样例

输入：

4 3
5 5 1 1

输出：

1

样例解释

只保留第 $2$ 个位置，得到序列 $(0,5,0,0)$。两个长度为 $3$ 的连续区间的最大值仍然都是 $5$，因此答案为 $1$。

附加样例 $\texttt{peak2.in/.ans}$、$\texttt{peak3.in/.ans}$、$\texttt{peak4.in/.ans}$ 分别满足测试点 $1\sim4$、$5\sim6$、$15\sim20$ 的限制。

数据范围

对于所有测试点，$1\le k\le n\le5000$，$1\le a_i\le10^9$。

特殊性质 $A$：序列 $a$ 中的元素两两不同。

特殊性质 $B$：$k=2$。

特殊性质 $C$：$k=3$。

特殊性质 $D$：$k=n-1$。