9
Problem E. 8. Строго возрастающая с m разрывами подпоследовательность
Input file name: m-gaps.in
Output file name: m-gaps.out
Time limit: 1 s
Memory limit: 256 MB

Необходимо из заданной числовой последовательности A, состоящей из n элементов, вычеркнуть минимальное число элементов, чтобы в оставшейся подпоследовательности каждый последующий элемент был строго больше предыдущего, кроме не более чем m пар соседних элементов (разрывов).

Input

Первая строка содержит целые числа n и m (0 ≤ m < n ≤ 30 000, m ≤ 100). Следующая строка содержит n элементов последовательности A, которые разделены пробелом (все числа целые, по модулю не превосходящие 1 000 000 000).

Output

Выведите одно целое число — длину наибольшей подпоследовательности.

Examples

m-gaps.in m-gaps.out
9 2
1 2 12 7 3 8 14 13 9
7
9 3
1 2 12 7 3 8 14 13 9
8