C++!! Upper bound
На вход подаются N целых чисел, а также набор из M запросов, каждый из которых — целое число. Ваша задача — для каждого запроса найти количество чисел из исходного набора, меньших либо равных заданному в запросе числу. Использовать встроенные функции бинарного поиска запрещено.
Входные данные
Первая строка содержит число N — количество элементов в массиве. 1≤N≤250000.
Вторая строка содержит N целых чисел Ai через пробел. −10^9≤Ai≤10^9.
Третья строка содержит число M — количество запросов. 1≤M≤250000.
Четвёртая строка содержит M целых чисел Qi через пробел. −10^9≤Qi≤10^9.
Выходные данные
Выведите единственную строку с M целыми числами — количествами чисел исходного массива, меньших либо равных соответствующему запросу.
Примеры
Ввод
5
1 5 3 2 1
2
4 3
Вывод
4 4
Ограничения
Время выполнения: 3 секунды