Given sequence of N integers, find the longest subsequence whose elements are ordered in an increasing order. Up to k exceptions that means at most k times, the next number in the sequence is smaller than previous one. Output should be the length of the longest such subsequence. In particular the question is a variant of LIS problem where at most k exceptions (restarts) are allowed.

Constraints:

3 <= N <= 10^6

1 <= K <= max{N-1,2000}

1 <= s[i] <=10^7

Time: 3 sec

Memory: 64 MB