P15849 [NOISG 2026 Finals] 3 Raptors

WhiteRaptor has finally found his own kind in TheRaptorLand! Unlike the plain WhiteRaptor, TheRaptorLand has an assortment of coloured raptors: the PinkRaptor, BlueRaptor and GreenRaptor. WhiteRaptor lined up all $n$ raptors in TheRaptorLand in a line, numbered from $1$ to $n$ from left to right. The $i$-th raptor from the left has colour $c[i]$. He wants to choose some raptors to keep him company in his basement forever. However, he is only able to do so by removing zero or more raptors from the left and right ends of the line, and keeping all raptors that remain. To ensure that no raptors that remained will be ostracised, he wants the difference between the frequency of the most common raptor colour and the frequency of the least common raptor colour to not exceed $k$. Note that if no raptors of a certain colour remained, the frequency of the least common raptor colour will be $0$. Help WhiteRaptor find the maximum number of raptors that he can keep!

Your program must read from standard input. The first line of input contains two integers $n$ and $k$. The second line of input contains $n$ space-separated integers $c[1], c[2], \dots, c[n]$.

Your program must print to standard output. Output one integer, the maximum number of raptors that he can keep.

### Sample Test Case 1 Explanation From raptor $3$ to raptor $9$, the number of raptors with $c[i] = 1, 2,$ and $3$ are $3, 3,$ and $1$ respectively. Since the difference between the maximum and minimum frequencies does not exceed $k = 2$, this set of raptors satisfies WhiteRaptor’s criterion. An example of an invalid set of raptors is from raptor $3$ to raptor $10$, as the addition of another raptor with $c[i] = 1$ causes the frequency of the most common colour to become $4$. The resulting difference between the maximum and minimum frequencies is $3$, which exceeds $k = 2$. It can be shown that $7$ is the largest number of raptors WhiteRaptor can keep that still satisfies his criterion. ### Sample Test Case 2 Explanation WhiteRaptor should choose the raptors from raptor $1$ to raptor $5$. ### Sample Test Case 3 Explanation Since any contiguous sequence of raptors will not contain a raptor with $c[i] = 3$, the frequency of the least common colour will always be $0$. This means that WhiteRaptor cannot select any non-empty sequence of raptors. Hence, the output is $0$. Note that this testcase satisfies Subtask 5 because we can assign $j = n$ (no colour-3 raptors will appear). ### Subtasks For all test cases, the input will satisfy the following bounds: - $1 \leq n \leq 200\,000$ - $0 \leq k \leq 200\,000$ - $1 \leq c[i] \leq 3$ for all $1 \leq i \leq n$ Your program will be tested on input instances that satisfy the following restrictions: | Subtask | Score | Additional Constraints | |:-:|:-:|:-:| | 0 | 0 | Sample test cases | | 1 | 5 | $n \leq 500$ | | 2 | 9 | $n \leq 2000$ | | 3 | 11 | $c[i] \leq 2$ | | 4 | 15 | $k = 0$ | | 5 | 16 | There exists a $1 \leq j \leq n$ such that $c[i] \ne 3$ for all $i \leq j$, and $c[i] = 3$ for all $i > j$ | | 6 | 20 | In any contiguous sequence of 3 or more raptors, colour 3 is the least common. | | 7 | 24 | No additional constraints |