| Автор: | А. Усманов | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt |
Существует много способов готовиться к олимпиадам по программированию. Один из них — решать задачи на сайте Timforces. На этом сайте есть рейтинг всех пользователей, составленный на основе количества решенных каждым пользователем задач. Нумерация мест в рейтинге начинается с 1, номера мест не повторяются. Чем больше задач пользователь решил, тем меньше его номер в рейтинге. Если два и более пользователей решили одинаковое количество задач, то они располагаются в произвольном порядке.
Алексей придумал понятие продвинутого пользователя. Продвинутыми считаются те пользователи, у которых количество решенных задач не меньше занимаемого места в рейтинге. Например, если пользователь занимает 3 место в рейтинге и при этом решил 5 задач, то он продвинутый, а если пользователь с 10 места решил лишь 9 задач, то он не продвинутый.
Алексей захотел несколько раз посчитать, какое максимальное количество продвинутых пользователей может получиться, если некоторые пользователи суммарно решат определённое количество задач.
В первой строке входного файла записано одно целое число N — количество пользователей на сайте Timforces.
Во второй строке записано N целых чисел ai — количество решенных задач у пользователя с i-го места в рейтинге.
В третьей строке записано одно целое число Q — количество вопросов Алексея.
Далее следует Q целых чисел pi — суммарное количество задач, решенных некоторыми пользователями.
Обратите внимание, что вопросы Алексея независимы. То есть, перед каждым запросом количество решенных задач и рейтинг такие же, как во входных данных.
Выведите Q целых чисел — ответы на каждый вопрос Алексея.
1 ≤ N, Q ≤ 105
0 ≤ ai, pi ≤ 109
В первом вопросе Алексея из первого примера пользователь с третьего места может решить одну задачу и станет продвинутым. Помимо этого, продвинутыми уже являются пользователи с первого и второго места.
Во втором вопросе из первого примера пользователь со второго места может решить 2 задачи, пользователь с третьего места — 4 задачи, пользователь с четвертого места — 5 задач. Тогда положение пользователей в рейтинге изменится. Например, на первом месте нового рейтинга будет пользователь с четвёртого места старого рейтинга и т.д. Количество задач у пользователей в новом рейтинге: 7 6 5 4. В таком случае все пользователи являются продвинутыми.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|