← 返回题目列表

Codeforces · 847/D

D. 狗展

中文机器翻译题面 查看原题

电视上的新狗节目将于下周开始。在表演中,狗需要展现出无底洞的胃、战略思维和自我保护的本能。您和您的狗被邀请与其他参与者竞争,您自然想获胜!

在节目中,狗需要吃尽可能多的碗狗粮(无底胃在这里有帮助)。犬只单独参赛,规则如下:

表演开始时,狗和碗位于一条线上。狗从位置 x = 0 开始,n 个碗位于位置 x = 1、x = 2、...、x = n。碗从左到右编号为 1 到 n。表演开始后,狗立即开始向右跑到第一个碗。

碗里的食物一开始还没有准备好吃,因为太热了(狗的自我保护本能阻止了吃)。更正式地说,狗可以在表演开始后 ti 秒或稍后吃第 i 个碗。

狗从位置x移动到位置x+1需要1秒。狗不允许向左移动,狗只能向右以每秒1个距离单位的匀速运行。当狗到达碗(例如,碗 i)时,可能出现以下情况:

- 食物已经冷却(即距离表演开始至少过了 ti 秒):狗立即吃掉食物并不停地向右跑,
- 食物是热的(即距离表演开始不到 ti 秒):狗有两个选择:等待第 i 个碗,吃完食物并在 ti 时刻继续跑,或者跳过第 i 个碗并继续向右跑,不停歇。

节目开始后 T 秒后结束。如果狗在 T 时刻拿到一碗食物,那么狗就不能吃它。如果狗跑到最后一个碗的右侧,则表演将在 T 秒前停止。

你需要帮助你的狗制定一个策略,在 T 秒内吃掉尽可能多的碗里的食物。

输入

第一行给出两个整数 - n 和 T (1 ≤ n ≤ 200 000, 1 ≤ T ≤ 2·109) - 食物碗的数量和狗停下来的时间。

下一行给出数字 t1, t2, ..., tn (1 ≤ ti ≤ 109),其中 ti 是第 i 碗食物准备好食用的时刻。

输出

输出一个整数——狗在 T 秒内能够吃掉的最大碗数。

示例

输入 #1

3 5
1 5 3

输出 #1

2

输入 #2

1 2
1

输出 #2

1

输入 #3

1 1
1

输出 #3

0

注意

在第一个例子中,狗应该跳过第二个碗来吃两个碗(第一个和第三个)。