Problem Description

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.

Input Format

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 Format

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

6 1 3
4 6 10 13 30 31

4

5 0 2
1 10 20 30 40

1

4 3 0
5 100 5 100

4

Hint

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