Задача C. Timforces ≡

Условие

Существует много способов готовиться к олимпиадам по программированию. Один из них — решать задачи на сайте Timforces. На этом сайте есть рейтинг всех пользователей, составленный на основе количества решенных каждым пользователем задач. Нумерация мест в рейтинге начинается с 1, номера мест не повторяются. Чем больше задач пользователь решил, тем меньше его номер в рейтинге. Если два и более пользователей решили одинаковое количество задач, то они располагаются в произвольном порядке.

Алексей придумал понятие продвинутого пользователя. Продвинутыми считаются те пользователи, у которых количество решенных задач не меньше занимаемого места в рейтинге. Например, если пользователь занимает 3 место в рейтинге и при этом решил 5 задач, то он продвинутый, а если пользователь с 10 места решил лишь 9 задач, то он не продвинутый.

Алексей захотел несколько раз посчитать, какое максимальное количество продвинутых пользователей может получиться, если некоторые пользователи суммарно решат определённое количество задач.

Формат входного файла

В первой строке входного файла записано одно целое число N — количество пользователей на сайте Timforces.

Во второй строке записано N целых чисел a_i — количество решенных задач у пользователя с i-го места в рейтинге.

В третьей строке записано одно целое число Q — количество вопросов Алексея.

Далее следует Q целых чисел p_i — суммарное количество задач, решенных некоторыми пользователями.

Обратите внимание, что вопросы Алексея независимы. То есть, перед каждым запросом количество решенных задач и рейтинг такие же, как во входных данных.

Формат выходного файла

Выведите Q целых чисел — ответы на каждый вопрос Алексея.

Ограничения

1 ≤ N, Q ≤ 10⁵

0 ≤ a_i, p_i ≤ 10⁹

Пояснение к примерам

В первом вопросе Алексея из первого примера пользователь с третьего места может решить одну задачу и станет продвинутым. Помимо этого, продвинутыми уже являются пользователи с первого и второго места.

Во втором вопросе из первого примера пользователь со второго места может решить 2 задачи, пользователь с третьего места — 4 задачи, пользователь с четвертого места — 5 задач. Тогда положение пользователей в рейтинге изменится. Например, на первом месте нового рейтинга будет пользователь с четвёртого места старого рейтинга и т.д. Количество задач у пользователей в новом рейтинге: 7 6 5 4. В таком случае все пользователи являются продвинутыми.

Примеры тестов

4
4 3 2 2
2
1 11

3 4

4
5 1 0 0
5
1 4 5 10 11

2 2 3 3 4