2023 年上海市大学生程序设计竞赛 - 七月赛

B. 音乐之城

单点时限: 2.0 sec

内存限制: 512 MB

谷米莱莉娅擅长音游。

她正在玩一款最新最热的1 key音游。音游是这样一种游戏:一首歌曲的音游谱会有若干个音符,它们会按顺序在特定时间到达判定线,而她需要在音符到达判定线音符的 $\pm t$ ms(含 $t$ ms)内点击屏幕,这样就可以击打音符。由于这款音游最新最热,如果点击屏幕的时候有多个音符都满足被击打的条件,那么它们都会被击打

现在她正在打的歌有 $n$ 个音符,对于第 $i$ 个音符来说,它会在 $a_i$ ms时刻到达判定线。由于谷米莱莉娅擅长魔法,她把她的手变成了打桩机,打桩机启动后每隔$x$ ms就会自动点击屏幕一次。

在音游里,击打尽量多的连续的音符 (即 combo ) 是很重要的。 由于这款音游最新最热,一次击打打空也不会降低 combo数。而如果错过了一个音符没有击打,那么重新开始计算连击 (即 combo 归零)。现在谷米莱莉娅已经启动了打桩机,她可以在任意一个整数时刻开始打歌(甚至在歌曲开始前),她想知道她能获得的最高combo是多少。

输入格式

输入第一行包含三个整数 $n,x,t$. $(1\le n \le 10^5, 0 \le t \le 10^9, 1 \le x \le 64)$

输入第二行包含$n$个整数 $a_i$. ($a_i$ 不严格单调递增且 $0 \le a_i \le 10^9$)

输出格式

输出仅包含一行一个非负整数,表示能获得的最高 combo。

样例

Input
5 10 20
20 20 20 20 20
Output
5
Input
10 59 7
101823754
150050892
302621085
495930340
495930399
495930458
495930517
495930576
663968656
811538591
Output
7
Input
10 59 5
79180333
106046332
354546568
734422155
783650879
913189318
934706414
934706473
934706532
965120264
Output
4