바리스타 폴의 커피콩 고르기

바리스타 폴 앞에 커피콩 $N$개가 한 줄로 놓여 있다. 폴은 이 중에서 몇 개를 골라 추출한다. 고른 콩은 원래 놓인 순서를 그대로 지킨다.

커피콩마다 종류를 나타내는 정수가 하나씩 붙어 있다. 고른 콩의 종류를 순서대로 적은 수열을 $A$라고 하자. 추출물의 질이 좋다는 것은 $2$ 이상인 모든 $i$에 대해 다음 두 조건 중 적어도 하나가 성립한다는 뜻이다.

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

질이 좋은 추출물 중에서 커피콩을 가장 많이 고를 때, 그 개수를 구하라.

첫째 줄에 $N$, $k$, $d$가 공백으로 구분되어 주어진다. ($1 \le N \le 5 \times 10^5$, $1 \le k, d \le 5 \times 10^5$)

둘째 줄에 커피콩의 종류를 놓인 순서대로 나타낸 길이 $N$의 수열 $S_1, S_2, \dots, S_N$이 주어진다. ($1 \le S_i \le 5 \times 10^5$)

질이 좋은 추출물에 들어가는 커피콩 개수의 최댓값을 출력한다.