eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Башня

Башня

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Город X состоит из n зданий, расположенных на одной прямой с запада на восток и пронумерованных с 1 до n. Каждое здание имеет разную высоту - целое число, соответственно h[1], h[2], ..., h[n]. Правительство города планирует построить башню, которая будет в том же ряду, что и здания (это может быть до первого здания, между любыми двумя зданиями или после последнего здания). Башня будет передавать сообщения гражданам. Башня должна иметь высоту H, которая должна отличаться от высот всех зданий.

Из-за некоторых странных технических идей, башня сможет передавать сигналы только на запад (к началу ряда зданий). Сигналы также странные - это лучи, которые движутся горизонтально (параллельно земле, которую мы рассматриваем как прямая линия) и излучаются со всей поверхности башни (сверху вниз). Поэтому можно представить себе, что башня излучает непрерывную полосу сигналов с шириной, равной высоте башни. Когда луч попадает в здание, он останавливается. Каждое здание принимает сигналы с помощью приемника, расположенного на его вершине. Здание получает сообщение, если по крайней мере один луч достигает его приемника.

Другими словами, здание номер i будет получать сообщения от башни если только: здание i расположено западнее башни; i не выше башни; и если не существует другого здания j между ними (j > i), которое выше здания i.

prb8564.gif

На рисунке сверху зданиями, получающими сообщения, будут 2, 5, 6 и 9.

Напишите программу, которая определит максимальное количество зданий, которые будут получать сообщения. Вам будет предоставлен ряд зданий в городе (фактически, их высоты) и высота башни. Конечно, башню следует расположить оптимально.

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

Первая строка содержит два числа: n (1n10^6) иd H (1H, h[i]10^9) - количество зданий и высота башни. Вторая строка содержит n положительных целых чисел - высоты зданий в городе, упорядоченные по номерам зданий (от первого до n - го)

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

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

Объяснение

На рисунке внизу приведено оптимальное размещение башни. Сообщения получат здания с номерами 2, 5, 6, 7 и 8.

prb8564_1.gif

Пример

Входные данные #1
12 180
200 170 130 90 150 140 40 30 100 160 50 110
Выходные данные #1
5
Источник 2016 VIII International autumn tournament in informatics, Shumen, Junior, Задача B