Башни
Город X состоит из n зданий, расположенных на одной прямой с запада на восток и пронумерованных с 1 до n. Каждое здание имеет разную высоту - целое число, соответственно h[1], h[2], ..., h[n]. Правительство города планирует построить башню, которая будет в том же ряду, что и здания (это может быть до первого здания, между любыми двумя зданиями или после последнего здания). Башня будет передавать сообщения гражданам. Башня должна иметь высоту H, которая должна отличаться от высот всех зданий.
Из-за некоторых странных технических идей, башня сможет передавать сигналы только на запад (к началу ряда зданий). Сигналы также странные - это лучи, которые движутся горизонтально (параллельно земле, которую мы рассматриваем как прямая линия) и излучаются со всей поверхности башни (сверху вниз). Поэтому можно представить себе, что башня излучает непрерывную полосу сигналов с шириной, равной высоте башни. Когда луч попадает в здание, он останавливается. Каждое здание принимает сигналы с помощью приемника, расположенного на его вершине. Здание получает сообщение, если по крайней мере один луч достигает его приемника.
Другими словами, здание номер i будет получать сообщения от башни если только: здание i расположено западнее башни; i не выше башни; и если не существует другого здания j между ними (j > i), которое выше здания i.
На рисунке сверху зданиями, получающими сообщения, будут 2, 5, 6 и 9.
Будет построена только одна башня, однако городское правительство получило предложение по k вариантам башни, каждая из которых имеет разную высоту (и имеет разную стоимость постройки). Предлагаемые башни нумеруются от 1 до k. Каждая из этих башен имеет свою высоту, которая также отличается от всех высот зданий в городе. Руководители города хотели бы знать максимальное количество зданий, которые будут получать сообщения, для каждой из предложенных k башен. Разумеется, расчеты должны быть сделаны при оптимальном размещении каждой башни.
Входные данные
Первая строка содержит два натуральных числа: n (1 ≤ n ≤ 10^6) и k (1 ≤ k ≤ 10^5) - количество зданий и количество предложенных башен. Вторая строка содержит n натуральных чисел - высоты зданий (1 ≤ высота каждого здания и предложенной башни ≤ 10^9) в городе, пронумерованных числами (от первой до n-ой).
Третья строка состоит из k натуральных чисел - высоты предложенных башен.
Выходные данные
В одной строке выведите k неотрицательных целых чисел: для каждой башни в третьей входной строке - максимальное количество зданий, которые будут получать сообщения, если башня будет построена с оптимальным размещением.
Объяснение
Оптимальные расположение каждой башни показаны на рисунках ниже.
