Вежі#8566

Вежі

1 секунда

256 мегабайтів

Легка

Місто $X$ складається з $n$ будівель, розташованих на одній прямій із заходу на схід і пронумерованих від $1$ до $n$ . Кожна будівля має унікальну висоту, позначену як $h_{1}, h_{2}, \dots, h_{n}$ h_1, h_2, \ldots, h_n. Уряд міста планує звести вежу на цій же прямій (перед першою будівлею, між будь-якими двома будівлями або після останньої будівлі). Вежа буде передавати повідомлення громадянам і повинна мати висоту $H$ , яка відрізняється від висот усіх будівель.

Через певні технічні особливості, вежа може передавати сигнали лише на захід (до початку ряду будівель). Сигнали поширюються у вигляді променів, які рухаються горизонтально (паралельно землі) і випромінюються з усієї поверхні вежі (зверху вниз). Таким чином, вежа випромінює безперервну смугу сигналів, ширина якої дорівнює висоті вежі. Коли промінь потрапляє в будівлю, він зупиняється. Кожна будівля має приймач на даху, який приймає сигнали. Будівля отримує повідомлення, якщо хоча б один промінь досягає її приймача.

Іншими словами, будівля номер $i$ отримує повідомлення від вежі, якщо вона розташована західніше вежі, не вища за вежу, і між нею та вежею немає іншої будівлі $j$ (де $j > i$ j > i), яка вища за будівлю $i$ .

На малюнку вище будівлі, які отримують повідомлення, це $2$ , $5$ , $6$ і $9$ .

Буде зведена лише одна вежа, але міське керівництво розглядає $k$ варіантів веж, кожна з яких має різну висоту (і різну вартість будівництва). Запропоновані вежі пронумеровані від $1$ до $k$ . Кожна з цих веж має висоту, яка відрізняється від висот усіх будівель у місті. Керівники міста хочуть дізнатися максимальну кількість будівель, які зможуть отримувати повідомлення для кожної з $k$ запропонованих веж. Розрахунки мають бути виконані з урахуванням оптимального розміщення кожної вежі.

Вхідні дані

Перший рядок містить два натуральних числа: $n$ ( $1 \leq n \leq 1 0^{6}$ 1 \leq n \leq 10^6) і $k$ ( $1 \leq k \leq 1 0^{5}$ 1 \leq k \leq 10^5) - кількість будівель і кількість запропонованих веж. Другий рядок містить $n$ натуральних чисел - висоти будівель ( $1 \leq$ висота кожної будівлі і запропонованої вежі $\leq 1 0^{9}$ \leq 10^9) у місті, пронумерованих від першої до $n$ -ої.

Третій рядок складається з $k$ натуральних чисел - висоти запропонованих веж.

Вихідні дані

В одному рядку виведіть $k$ невід'ємних цілих чисел: для кожної вежі з третього вхідного рядка - максимальну кількість будівель, які будуть отримувати повідомлення, якщо вежа буде побудована з оптимальним розміщенням.

Приклади

Приклад 1

Примітка

Оптимальні розташування кожної вежі показані на малюнках нижче.