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

Башни

Башни

Лимит времени 1 секунда
Лимит использования памяти 256 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.

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

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

Первая строка содержит два натуральных числа: n (1n10^6) и k (1k10^5) - количество зданий и количество предложенных башен. Вторая строка содержит n натуральных чисел - высоты зданий (1 ≤ высота каждого здания и предложенной башни ≤ 10^9) в городе, пронумерованных числами (от первой до n-ой).

Третья строка состоит из k натуральных чисел - высоты предложенных башен.

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

В одной строке выведите k неотрицательных целых чисел: для каждой башни в третьей входной строке - максимальное количество зданий, которые будут получать сообщения, если башня будет построена с оптимальным размещением.

Объяснение

Оптимальные расположение каждой башни показаны на рисунках ниже.

prb8566.gif
prb8566_1.gif

Пример

Входные данные #1
16 3
200 170 155 90 150 140 40 30 185 160 50 110 80 15 70 35
165 180 120
Выходные данные #1
5 6 4
Источник 2016 VIII International autumn tournament in informatics, Shumen, Senior, Задача A