Problem Description

Given an integer sequence of length $N$: $A_{1}, A_{2}, \cdots, A_{N}$. You now have one chance to modify $K$ consecutive numbers in it to any same value. Please compute how to modify it so that the longest non-decreasing subsequence of the modified sequence is as long as possible, and output this maximum length.

A longest non-decreasing subsequence means a subsequence of the sequence, where each number in the subsequence is not less than the number before it.

Input Format

The first line contains two integers $N$ and $K$.

The second line contains $N$ integers $A_{1}, A_{2}, \cdots, A_{N}$.

Output Format

Output one line containing one integer, representing the answer.

5 1
1 4 2 8 5

4

Hint

For $20\%$ of the testdata, $1 \leq K \leq N \leq 100$.

For $30\%$ of the testdata, $1 \leq K \leq N \leq 1000$.

For $50\%$ of the testdata, $1 \leq K \leq N \leq 10000$.

For all testdata, $1 \leq K \leq N \leq 10^{5}$, $1 \leq A_{i} \leq 10^{6}$.

Lanqiao Cup 2022 Provincial Contest, Group A, Problem G.

Translated by ChatGPT 5