P16796 [Lanqiao Cup 2026 National B] LED Strip Repair

Xiaolan has a circular LED strip. There are $N$ LEDs on the strip in clockwise order, and the brightness of the $i$-th LED is $A_i$. If the absolute difference in brightness between two adjacent LEDs is greater than $K$, then this adjacent pair is called unstable. Since the strip is circular, the $N$-th LED and the $1$-st LED are also adjacent. Xiaolan may first choose a cut between any two adjacent LEDs to open the circular strip into a line. Then, he will choose a consecutive segment of LEDs in this line to display. If the chosen display segment contains $L$ LEDs, then there are $L-1$ adjacent pairs inside the segment that need to be checked. Xiaolan can repair at most $M$ unstable adjacent pairs among them. The display segment is valid if and only if the number of unstable adjacent pairs inside the segment does not exceed $M$. Please compute, when the cut and the display segment can be chosen freely, the maximum number of consecutive LEDs Xiaolan can display.

The first line contains three integers $N, M, K$, representing the number of LEDs, the maximum number of unstable adjacent pairs that can be repaired, and the threshold for stable brightness difference. The second line contains $N$ integers $A_1, A_2, \dots, A_N$, where $A_i$ is the brightness of the $i$-th LED.

Output one line containing one integer, which is the maximum number of consecutive LEDs that can be selected.

### Sample Explanation 1 You can cut between the $6$-th and the $1$-st LED. After opening it, choose LEDs $1$ to $4$, with brightness values $4, 6, 10, 13$ in order. There are $3$ adjacent pairs in this segment: $4$ and $6$ are stable, $6$ and $10$ are unstable, and $10$ and $13$ are stable. After repairing the pair $6$ and $10$, you can display $4$ consecutive LEDs. For any segment of $5$ consecutive LEDs, the segment will contain at least $2$ unstable adjacent pairs, which exceeds $M = 1$, so the answer is $4$. ### Sample Explanation 2 As long as the display segment length is at least $2$, an unstable adjacent pair will appear in the segment. Since $M = 0$, no unstable adjacent pairs can be repaired, so at most one LED can be displayed. ### Sample Explanation 3 By choosing a suitable cut, you can display all $4$ LEDs. After opening it, there are only $3$ adjacent pairs in the segment that need to be checked. They are all unstable, but they can all be repaired, so the answer is $4$. ### Constraints and Notes for Test Cases For $30\%$ of the test cases, $1 \le N \le 200$. For $60\%$ of the test cases, $1 \le N \le 5000$. For all test cases, $1 \le N \le 2 \times 10^5$, $0 \le M \le N-1$, $0 \le K \le 10^9$, $1 \le A_i \le 10^9$. Translated by ChatGPT 5