Almost-K Increasing Subsequence

Interview

Time limit1sMemory limit256 MB

Summary

Find the longest subsequence of a given sequence that has at most K positions where consecutive elements decrease.

Level: Medium6 of 10
Topics: Dynamic programming, Array, Binary search, Sorting
Solved: No attempts yet

Problem

A sequence a1, a2, ... , an is given. We can delete zero or more numbers from this sequence to make a new sequence b1, b2, ... , bm. We call the sequence b1, b2, ... , bm a Subsequence of the sequence a1, a2, ... , an. For example, the Subsequences of the sequence (1,2,4,5) include (1), (2, 5), and (1, 2, 4, 5).

Given a sequence A = a1, a2, ... , an and K, we want to find the length of the Longest Almost-K Increasing Subsequence of A. The Longest Almost-K Increasing Subsequence is the longest among the Almost-K Increasing Subsequences, and an Almost-K Increasing Subsequence is defined as follows.

Suppose the sequence B = b1, b2, ... , bm is a Subsequence of the sequence A. If, for every i = 1, 2, ... , m−1, the number of indices i with bi > bi+1 is at most K, then B is defined to be an Almost-K Increasing Subsequence of A.

Input

The first line contains n and K (1 ≤ n ≤ 500, 0 ≤ K ≤ n).

The second line contains the integers a1, a2, ... , an (1 ≤ ai ≤ 109).

Output

Print the length of the Longest Almost-K Increasing Subsequence of A.

Hint

In the first example, the Almost-0 Increasing Subsequences are (1, 2, 3, 5) and (1, 2, 3, 4), both of length 4.

In the second example, an Almost-1 Increasing Subsequence is (1, 2, 3, 5, 4), whose length is 5.

Examples2

Example 1
Input
```
5 0
1 2 3 5 4
```
Expected output
```
4
```
Example 2
Input
```
5 1
1 2 3 5 4
```
Expected output
```
5
```