Верхняя граница
Дан отсортированный массив из
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