Верхняя граница
Дан отсортированный массив из n целых чисел. Необходимо ответить на q запросов. Каждый запрос формулируется так: «Какое первое число, которое больше, чем x, встречается в данном списке?».
Входные данные
Первая строка ввода содержит два целых числа n (2 ≤ n ≤ ) и q (1 ≤ q ≤ ).
Следующая строка содержит n целых чисел, разделённых пробелами: ( ≤ ≤ ), расположенных в порядке возрастания.
Последняя строка содержит q запросов ( ≤ < ), разделённых пробелами.
Выходные данные
Программа должна вывести q строк, где каждая строка содержит ответ на соответствующий запрос.
Примеры
Входные данные | Выходные данные |
|---|---|
6 3 2 7 9 10 20 30 8 20 1 | 9 30 2 |
Подсказка
В классической реализации двоичного поиска рассматривается диапазон [l; r), где l включён, а r нет. Иногда полезнее использовать (l; r] — исключая l и включая r. Для этого придётся немного изменить логику вычисления l, r и mid.
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB