EduBrick

E. Первый больший

1000 мс · 256 МБ · всё или ничего

Дан неубывающий массив из nn чисел. Для каждого из qq запросов xx найдите номер первого элемента, строго большего xx. Нумерация с единицы; если такого элемента нет, выведите −1-1.

Это ровно то место, где двоичный поиск чаще всего ломается: перепутанные строгое и нестрогое сравнение дают ответ, отличающийся на единицу, и на маленьких тестах ошибка не видна.

Формат ввода

Первая строка содержит числа nn и qq (1≤n,q≤1051 \le n, q \le 10^5).

Вторая строка содержит nn чисел в порядке неубывания, третья — qq запросов. Все числа целые и по модулю не превосходят 10910^9.

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

Для каждого запроса выведите одно число — номер первого элемента, строго большего запроса, или −1-1.

Примеры

ввод
5 4
1 3 3 3 7
0 3 7 8
вывод
1
5
-1
-1
Войдите, чтобы отправлять решения.