Пороговая оценка в журнале

В электронном журнале учитель отсортировал все полученные за четверть баллы по возрастанию, чтобы быстро отвечать на вопросы вида «а кто набрал хотя бы X?».

Для каждого запроса X нужно найти самый ранний (с минимальным номером) элемент в этом отсортированном списке, который не меньше X.

Если все баллы меньше X — такого элемента нет.

Формат ввода

В первой строке даны два целых числа n и q — количество баллов в списке и количество вопросов. Во второй строке даны n целых чисел a1, a2, ..., an — баллы, отсортированные по неубыванию. Далее идут q строк, в каждой одно целое число x — порог.

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

Для каждого запроса выведите одно число — 1-базовый индекс первого элемента ai, для которого ai >= x. Если такого элемента нет, выведите 0.

Ограничения

• 1 ≤ n ≤ 20000
• 1 ≤ q ≤ 20000
• 1 ≤ ai ≤ 10^6
• 1 ≤ x ≤ 10^6
• Массив во входе уже отсортирован по неубыванию.

Пример

Ввод:

5 4
10 10 12 15 20
9
10
13
21

Вывод:

1
1
4
0

Ключевое наблюдение: список уже отсортирован, значит ответ для запроса X — это первый индекс, где a[i] >= X. Эту операцию часто называют lower_bound.

Почему работает бинарный поиск: условие a[i] >= X по индексу монотонно — пока элементы меньше X, ответ «нет», а начиная с некоторого места — «да». На монотонности бинарный поиск и держится.

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

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

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

Частая ошибка: неправильно обработать границы (например, делать r = n-1 и зациклиться) или забыть про дубликаты — нужно искать именно первый подходящий элемент, поэтому при a[m] >= X двигаем r, а не l.