P16318 [ICPC 2023 Jinan R] Rainbow Subarray

"Rainbow Sequence" is a tense and exciting board game involving luck and auctions. Players can rely on luck to draw more cards, or use money to buy other cards. The goal is to form the longest possible number sequence using cards of each color. Next, we consider a problem related to this game. :::align{center}  A photo taken by Instagram user @freethemeeple ::: Given a sequence of length $n$, $a_1, a_2, \cdots, a_n$, we call its contiguous subarray $a_l, a_{l + 1}, a_{l + 2}, \cdots, a_r$ a rainbow subarray if for all $l \le i < r$, it satisfies $a_{i + 1} - a_i = 1$. In particular, a subarray of length $1$ is always a rainbow subarray. You can perform at most $k$ operations. In each operation, you can increase or decrease one element in the sequence by $1$. Find the maximum possible length of the longest rainbow subarray after the operations.

There are multiple test cases. The first line contains an integer $T$ indicating the number of test cases. For each test case: The first line contains two integers $n$ and $k$ ($1 \le n \le 5 \times 10^5$, $0 \le k \le 10^{15}$), representing the length of the sequence and the maximum number of operations you may perform. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$), representing the sequence. It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \times 10^5$.

For each test case, output one integer per line, representing the maximum possible length of the longest rainbow subarray after performing at most $k$ operations.

For the first sample, we can perform $4$ operations and change the sequence to $\{7, 3, 4, 5, 6, 11, 7\}$. The longest rainbow subarray is $\{3, 4, 5, 6\}$, so the answer is $4$. For the second sample, we cannot perform any operations. The longest rainbow subarray is $\{3, 4, 5\}$, so the answer is $3$. For the third sample, we can perform $6$ operations and change the sequence to $\{-1, 0, 1, 2, 3\}$. The entire sequence is a rainbow subarray, so the answer is $5$. Translated by ChatGPT 5