F. Трудный выбор
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваня учится на ФИИТ в УрФУ, где каждый семестр студенты делают командные проекты. У Вани много друзей в группе, но у каждого свои требования. Например, если позвать в команду Петю, то должен прийти и Алёша, иначе Петя не придёт. Ваня по данным требованиям смог выяснить, что у него есть целых $$$N$$$ вариантов, кого пригласить. Каждый из способов он описал в виде величины $$$A_i$$$ — количество друзей в выборке под номером $$$i$$$.

Но это было полбеды! Ведь после того, как он с друзьями соберёт команду, нужно будет выбрать того, кто будет представлять проект на защите. Все ребята любят программировать, и никто не хочет заниматься презентацией, поэтому они договорились, что защищает проект тот, кого выберут по считалочке.

Ваня, будучи организатором этого выбора, должен проводить этот расчёт. Чтобы выбрать ответственного по считалочке, он выстраивает людей по кругу и начинает считать от себя, считая по одному слову на человека. На кого попадёт последнее слово, тот и защищает проект. Иван знает $$$Q$$$ считалочек. Считалочка номер $$$j$$$ состоит из $$$B_j$$$ слов. Он решил узнать, насколько удачной будет каждая из них. Для этого он ввёл понятие хорошей компании одногруппников — таковой она является, если в ней он не будет защищать проект при использовании данной считалочки.

Ваня хочет уже начать писать код для проекта вместо поиска идеальной считалочки, поэтому он обратился к вам, чтобы вы помогли ему вычислить ответ. Ему нужно для каждой считалочки найти минимальный номер хорошей группы.

Входные данные

В первой строке задано целое число $$$N$$$ — количество групп из друзей Вани ($$$1 \le N \le 10^5$$$).

Во второй строке записаны $$$N$$$ целых чисел $$$A_i$$$ — размеры $$$i$$$-й группы ($$$1 \le A_i \le 10^7$$$).

В третьей строке дано целое число $$$Q$$$ — количество считалочек ($$$1 \le Q \le 10^6$$$).

В следующих $$$Q$$$ строках записано по одному целому числу $$$B_j$$$ — количество слов в $$$j$$$-й считалочке ($$$1 \le B_j \le 10^7$$$).

Выходные данные

Выведите $$$Q$$$ строк, где $$$j$$$-я строка содержит одно целое число — минимальный номер хорошей группы для считалочки под номером $$$j$$$ или $$$-1$$$, если таковой нет.

Система оценки

$$$$$$ \begin{array} {|c|c|c|c|}

\hline \textbf{Подзадача} & \textbf{Баллы} & \textbf{Ограничения} & \textbf{Необх. подзадачи} \\ \hline 1 & 10 & N, Q \le 100; A_i, B_j \le 10^3 & \\ \hline 2 & 30 & N, Q \le 10^3; A_i, B_j \le 10^6 & 1 \\ \hline 3 & 16 & N \le 5000, Q \le 10^5; A_i, B_j \le 10^6 & 1, 2 \\ \hline 4 & 16 & N \le 10^5, Q \le 5000; A_i, B_j \le 10^6 & 1, 2 \\ \hline 5 & 15 & N, Q \le 10^5; A_i, B_j \le 10^6 & 1, 2, 3, 4 \\ \hline 6 & 13 & N \le 10^5, Q \le 10^6; A_i, B_j \le 10^7 & 1, 2, 3, 4, 5 \\ \hline \end{array}$$$$$$

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

Пример
Входные данные
3
1 2 5
3
3
7
12
Выходные данные
2
-1
1
Примечание

Объяснение примера:

Пусть первая считалочка будет «Выступать будешь ты».

Если мы возьмём первую группу, то Ваня и Вася будут стоять по кругу. Считалочка будет воспроизводиться следующим образом: («Выступать», Ваня), («будешь», Вася), («ты», Ваня). Т.е. Ваня будет выступать с докладом.

Если возьмём вторую группу, то у нас будет круг: Ваня, Валя, Витя. В таком случае будет следующая ситуация: («Выступать», Ваня), («будешь», Валя), («ты», Витя) — в этом случае выступает не Ваня, а значит группа хорошая и она будет ответом.

Для второй считалочки для всех трёх групп в конце будет Ваня, а значит ответ $$$-1$$$.

Для третьей считалочки первая группа уже хорошая.