#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Longest Ones After Flips - Classic Problems | Repovive

CLS58. Longest Ones After Flips

2s256 MB

Given a binary array, flip at most $k$ zeros to ones. Find the maximum length of a contiguous segment containing only ones after the flips.

Constraints

$1 \le n \le 2 \cdot 10^5$
$0 \le k \le n$
$a_i \in \{0,1\}$

Input

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

Output

len_{\max}

Samples

Input

8 2
1 0 1 1 0 0 1 1

Explanation

Flip the zeros at positions 5 and 6. Then positions 3 through 8 are all ones, giving length 6.

Output

Input

5 0
1 1 0 1 1

Explanation

No flips are allowed, so the longest existing all-one block has length 2.

Output

Input

4 4
0 0 0 0

Explanation

All four zeros may be flipped, so the entire array becomes a block of length 4.

Output

Given a binary array, flip at most $k$ zeros to ones. Find the maximum length of a contiguous segment containing only ones after the flips.

$1 \le n \le 2 \cdot 10^5$
$0 \le k \le n$
$a_i \in \{0,1\}$

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

len_{\max}