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

Description

XXX自从被关进精神病院，学会了一种新游戏，这天，他从精神病院逃脱，回到了XMU，并且以ACM队队长的名义举行了一个趣味比赛，邀请了全校同学参加。
这个游戏是这样的：
所有的同学们站成一排，接着XXX从中剔除出连续并排（即相邻）的M个同学，让他们退出游戏，使得剩下的同学们的身高所组成的序列拥有最长上升子序列（即从这个序列中按顺序挑出若干个身高，满足身高递增且序列长度最长）。
由于XXX在精神病院呆久了，神智不清，口齿也不清，所以他请你帮他计算出，最优挑选策略下，剔除相邻的M个同学之后，剩下同学的身高所组成的序列的最长上升子序列长度。

举个例子，假设现在有5个小朋友，身高分别为4 3 6 7 5，需要剔除2个同学，那么可以剔除身高为6 7的小朋友，剩下4 3 5，那么4 3 5的最长上升子序列是3 5或者4 5，最长上升子序列的长度为2。当然你也可以不剔除6 7而改为剔除4 3，那么剩下的为6 7 5，最长上升子序列为6 7，长度也为2。还可以剔除3 6 或 7 5，同样长度为2。

Format

Input

包含多组测试数据。
每组测试数据第一行有两个正整数N和M，表示有N(N<=100000)个小朋友，要从中剔除连续的M(0<=M<=N)个小朋友。
接下来一行N个整数，表示N个小朋友的身高（不超过1 600 000 000）

Output

对于每组测试数据，输出一行一个数，表示题目描述的最长上升子序列长度。

Sample 1

Input

8 2
2 3 4 6 1 2 3 4
5 2
4 3 6 7 5
6 3
1 3 5 9 6 2

Output

4
2
3

Limitation

1s, 128MB for each test case.

Hint

Source

Coolxxx