D. Дог-шоу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Очень скоро на ТВ выйдет новое шоу с участием собак и их хозяев — Дог-Шоу. На шоу от собак требуется продемонстрировать бездонный желудок, стратегическое мышление и инстинкт самосохранения. Вы и ваша собака приглашены на шоу, и, конечно же, вы хотите выиграть!

Чтобы победить на шоу, собака должна съесть как можно больше мисок с едой (в чём поможет бездонный желудок). Собаки соревнуются отдельно друг от друга по следующим правилам:

В начале шоу на прямой находится собака в точке x = 0, а в точках x = 1, x = 2, ..., x = n находятся n мисок с едой. Миски пронумерованы от 1 до n слева направо. Как только начинается шоу, собака начинает бежать направо к ближайшей миске.

Еда в мисках в начале шоу слишком горячая и собака не может её съесть, пока она не остынет (инстинкт самосохранения мешает этому). Про i-ю из мисок известно, что еда в ней остынет через ti секунд после начала шоу, и в этот момент собака сможет её съесть.

Собака съедает миску еды мгновенно. Собака перемещается от точки x до точки x + 1 за одну секунду. При этом собаке запрещено двигаться влево, она перемещается исключительно вправо и всегда со скоростью 1 единица расстояния в секунду. Когда собака достигает миски с едой, возможны следующие варианты:

  • еда уже остыла, тогда собака мгновенно съедает еду и без какой-либо остановки продолжает двигаться вправо;
  • еда ещё не остыла, тогда собака либо останавливается и ожидает, пока еда остынет, затем съедает её и тут же начинает двигаться вправо, либо без какой-либо остановки продолжает двигаться вправо, пропустив миску с едой.

Шоу останавливается через T секунд после начала. Если собака достигает миски с едой в момент ровно T, то она уже не успевает её съесть. Если до истечения T секунд собака убежала за самую правую из мисок, шоу останавливают досрочно.

Вы должны помочь вашей собаке составить стратегию, которая позволит ей съесть максимальное количество мисок с едой за T секунд.

Входные данные

В первой строке даны два целых числа n и T (1 ≤ n ≤ 200 000, 1 ≤ T ≤ 2·109) — количество мисок с едой и время, по истечении которого собака будет остановлена.

Во второй строке дана последовательность t1, t2, ..., tn (1 ≤ ti ≤ 109), где ti равно моменту времени, когда еда в i-й миске остынет, и собака сможет её съесть.

Выходные данные

Выведите одно целое число — максимальное количество мисок с едой, которые собака сможет съесть за T секунд.

Примеры
Входные данные
3 5
1 5 3
Выходные данные
2
Входные данные
1 2
1
Выходные данные
1
Входные данные
1 1
1
Выходные данные
0
Примечание

В первом примере собака должна пропустить вторую миску, чтобы успеть поесть из двух — из первой и из третьей.