Problem 4A. 制定城市旅行计划

时间限制：1000ms

内存限制：128MB

故事背景

朱朱最近干外卖赚了不少钱，打算给自己放\(N\)天假期。在导游小季的推荐下， 朱朱打算到各地旅游观光。他计划在接下来的\(N\)天内，每天去一个城市旅行。

但是他有一个问题：朱朱的假期太长，在旅行的时候，可能重复去他之前去过的城市。他想在出发前就确定一个旅行计划，以确保不会在相隔很接近的时间内两次去同一个城市。

每个城市都对应一个正整数编号，旅行计划确定了去城市的先后顺序，构成一个整数数组 \(plans[N]\)，其中每个元素\(plans[i]\)代表第\(i\ \)天去的城市。

如果计划中出现第\(i\)天和第\(j(j\geq i+1)\)天去同一个城市，且它们之间相距天数\(j-i\leq k\ \)，则代表这个计划不合理；

与之对应的，若计划中没有去相同的城市、或者去相同城市的相距天数均大于\(k\)，则表示这个计划合理。

例如下面计划中：\(N=6\)，一共要去三个不同的城市，\(k=2\)，这个计划是合理的。例如，\(i=0\)天和 \(i=3\)天去同一个城市7，相距天数为\(3>2\)。

现在，导游小季给出了一个旅行计划，请你判断这个计划是否合理。

输入

输入两个正整数\(N,k\)，代表假期天数为\(N\),要求的相距天数\(k\)。

接着输入\(N\)个整数，构成小季提出的旅行计划数组\(plans[N]\)

输出

若旅行计划合理输出1，不合理输出0。

示例

示例1：

输入：

6 2
7 13 80 7 13 80

输出：

1

示例2：

输入：

26 0
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 4

输出：

1

示例3：

输入：

20 5 
5 6 5 7 8 9 10 11 5 6 12 13 14 5 6 15 16 17 18 5

输出：

0

数据范围

• 对于 100% 数据，\(0 \leq k< n \leq 100\) , \(plans[i] \in [0,1000]\)
• 注意，本题当然可以使用\(O(n^2)\)的暴力解法求解，你能否想到时间复杂度更低的算法？