Paul the barista picks coffee beans

Paul the barista has $N$ coffee beans laid out in a row. He picks some of them and brews them. The picked beans keep the order they were laid out in.

Each bean carries one integer that names its kind. Write the kinds of the picked beans in order as a sequence $A$. The extraction has good quality when at least one of the two conditions below holds for every $i$ with $i \ge 2$.

• $A_{i-1} \equiv A_i \pmod k$
• $A_{i-1} - d \le A_i \le A_{i-1} + d$

Find the largest number of beans Paul can pick while the quality stays good.

The first line contains $N$, $k$, and $d$, separated by spaces. ($1 \le N \le 5 \times 10^5$, $1 \le k, d \le 5 \times 10^5$)

The second line contains a sequence $S_1, S_2, \dots, S_N$ of length $N$ giving the kind of each bean in the order the beans are laid out. ($1 \le S_i \le 5 \times 10^5$)

Print the largest number of beans in a good extraction.