Полка с учебниками: первый не ниже

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

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

Если такого учебника нет (все ниже x), выведи 0.

Формат ввода

В первой строке даны два целых числа n и q — число учебников на полке и число запросов. Во второй строке даны n целых чисел a1, a2, ..., an — высоты учебников. Гарантируется, что a1 ≤ a2 ≤ ... ≤ an. В следующих q строках дано по одному целому числу x — запрос.

Формат вывода

Выведи q строк. В каждой строке выведи одно число — минимальный индекс i (нумерация с 1), такой что ai ≥ x. Если такого i не существует, выведи 0.

Ограничения

• 2 ≤ n ≤ 16000
• 1 ≤ q ≤ 16000
• -10^9 ≤ ai ≤ 10^9
• -10^9 ≤ x ≤ 10^9
• Массив a отсортирован по неубыванию.

Пример

Ввод

5 4
1 3 3 7 10
0
3
4
11

Вывод

1
2
4
0

Ключевое наблюдение: массив высот отсортирован по неубыванию. Значит, если на какой-то позиции высота уже ≥ x, то и все правее тоже ≥ x. И наоборот: если a[i] < x, то все левее точно не подходят. Это ровно ситуация для двоичного поиска по «границе».

Нужно найти первый подходящий элемент — это стандартная версия двоичного поиска lower_bound: ищем минимальный индекс i, где условие a[i] >= x становится истинным.

План решения:

• Для каждого запроса x заведите два указателя l = 0, r = n и рассматривайте полуинтервал [l, r).
• Пока l < r:
• m = (l + r) // 2.
• Если a[m] >= x, то ответ может быть в левой части, сдвигаем r = m.
• Иначе элемент слишком маленький, сдвигаем l = m + 1.
• После цикла l — это первая позиция, где мог бы стоять элемент ≥ x.
• Если l == n, подходящего нет → печатаем 0, иначе печатаем l + 1 (переход к нумерации с 1).

Мини-сниппет правила сдвига: if a[m] >= x: r = m else: l = m + 1

Сложность: на один запрос O(log n), на все запросы O(q log n), памяти O(1) сверх массива.

Частая ошибка: путать границы (делать [l, r] вместо [l, r)) и из-за этого получать бесконечный цикл или ответ «второй подходящий» при равных элементах (например, для x=3 в [1,3,3,7] нужно вернуть первый 3).