电视上的新狗节目将于下周开始。在表演中,狗需要展现出无底洞的胃、战略思维和自我保护的本能。您和您的狗被邀请与其他参与者竞争,您自然想获胜!
在节目中,狗需要吃尽可能多的碗狗粮(无底胃在这里有帮助)。犬只单独参赛,规则如下:
表演开始时,狗和碗位于一条线上。狗从位置 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
注意
在第一个例子中,狗应该跳过第二个碗来吃两个碗(第一个和第三个)。