Longest Even Contiguous Subsequence (small)

Interview

Time limit1sMemory limit1024 MB

Summary

Delete at most K elements from a sequence, then report the longest contiguous run of even numbers possible.

Level: Medium5 of 10
Topics: Sliding window, Two pointers, Array, Greedy
Solved: No attempts yet

Problem

There is a sequence $S$ of length $N$ . Every element of $S$ is a positive integer.

You may pick an element at any position in $S$ and delete it, at most $K$ times in total.

For example, suppose $S$ is given as follows.

S : 1 2 3 4 5 6 7 8

If you delete the 4th element, 4, the sequence becomes the following.

S : 1 2 3 5 6 7 8

Given a sequence obtained by deleting at most $K$ elements from $S$ , find the maximum length of a contiguous subsequence consisting only of even numbers.

Input

The first line contains the length $N$ of the sequence $S$ and the maximum number of deletions $K$ , separated by a space.

The second line contains the $N$ integers that make up $S$ , separated by spaces.

Output

Print the maximum length of a contiguous subsequence consisting only of even numbers in a sequence obtained by deleting at most $K$ elements from $S$ .

Constraints

$1 \le N \le 50,000$
$1 \le K \le 100$
$1 \le$ element value $\le 10^6$

Examples1

Example 1
Input
```
8 2
1 2 3 4 5 6 7 8
```
Expected output
```
3
```