P8776 [Lanqiao Cup 2022 NOI Qualifier A] Longest Non-decreasing Subsequence

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.

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

Output one line containing one integer, representing the answer.

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