Dog Show

题意翻译

下星期将会有一个由狗参加的综艺节目，你的狗有幸被选中了。自然的，你想使得你的狗获胜。 在这个节目中，狗的任务是吃掉尽可能多的狗粮。狗们的比赛是分开进行的，规则如下： 一开始，有$n$只盛放着狗粮的碗排列在一条直线上，狗一开始在起点$x=0$处，这些碗依次坐落在$x=1,x=2,...,x=n$处，标号依次为$1$至$n$。当节目开始后，狗将会立即向右跑向第一只碗。 碗里的狗粮并不是一开始就可以吃的，因为它们太烫了。在比赛开始后的第$t_i$秒，狗才能去吃第$i$只碗里的狗粮。 狗需要用$1$秒的时间来向右从$x$坐标移动到$x+1$坐标，狗不可以向左走。当狗遇到一碗狗粮时，有两种不同情况： 狗粮已经冷却：此时狗不需要花费任何时间来吃掉这碗狗粮。 狗粮还未冷却：此时狗可以在原地等候直到狗粮冷却，或者直接放弃这碗狗粮继续向右行动。 $T$秒后节目将结束，此时狗不能再移动或者吃狗粮。如果狗在$T$秒前早已达到第$n$只碗的右边，那么节目可以提前结束。 你的任务是最大化狗在$T$秒内吃掉的狗粮数量。 输入格式：第一行两个数$n(1\leq n\leq200000)$和$T$。第二行$n$个数$t_i$。意义详见问题描述。 输出格式：一个数表示你的答案。

题目描述

A new dog show on TV is starting next week. On the show dogs are required to demonstrate bottomless stomach, strategic thinking and self-preservation instinct. You and your dog are invited to compete with other participants and naturally you want to win! On the show a dog needs to eat as many bowls of dog food as possible (bottomless stomach helps here). Dogs compete separately of each other and the rules are as follows: At the start of the show the dog and the bowls are located on a line. The dog starts at position $ x=0 $ and $ n $ bowls are located at positions $ x=1,x=2,...,x=n $ . The bowls are numbered from $ 1 $ to $ n $ from left to right. After the show starts the dog immediately begins to run to the right to the first bowl. The food inside bowls is not ready for eating at the start because it is too hot (dog's self-preservation instinct prevents eating). More formally, the dog can eat from the $ i $ -th bowl after $ t_{i} $ seconds from the start of the show or later. It takes dog 1 second to move from the position $ x $ to the position $ x+1 $ . The dog is not allowed to move to the left, the dog runs only to the right with the constant speed 1 distance unit per second. When the dog reaches a bowl (say, the bowl $ i $ ), the following cases are possible: - the food had cooled down (i.e. it passed at least $ t_{i} $ seconds from the show start): the dog immediately eats the food and runs to the right without any stop, - the food is hot (i.e. it passed less than $ t_{i} $ seconds from the show start): the dog has two options: to wait for the $ i $ -th bowl, eat the food and continue to run at the moment $ t_{i} $ or to skip the $ i $ -th bowl and continue to run to the right without any stop. After $ T $ seconds from the start the show ends. If the dog reaches a bowl of food at moment $ T $ the dog can not eat it. The show stops before $ T $ seconds if the dog had run to the right of the last bowl. You need to help your dog create a strategy with which the maximum possible number of bowls of food will be eaten in $ T $ seconds.

输入输出格式

输入格式

Two integer numbers are given in the first line - $ n $ and $ T $ ( $ 1<=n<=200000 $ , $ 1<=T<=2·10^{9} $ ) — the number of bowls of food and the time when the dog is stopped. On the next line numbers $ t_{1},t_{2},...,t_{n} $ ( $ 1<=t_{i}<=10^{9} $ ) are given, where $ t_{i} $ is the moment of time when the $ i $ -th bowl of food is ready for eating.

输出格式

Output a single integer — the maximum number of bowls of food the dog will be able to eat in $ T $ seconds.

输入输出样例

输入样例 #1

3 5
1 5 3

输出样例 #1

2

输入样例 #2

1 2
1

输出样例 #2

1

输入样例 #3

1 1
1

输出样例 #3

0

说明

In the first example the dog should skip the second bowl to eat from the two bowls (the first and the third).