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

Знаменитый писатель Велепин очень продуктивен. Совсем недавно он подписал контракт с известным изданием, и теперь за $$$i$$$-й год ему нужно написать $$$k_i$$$ романов. Для него это вообще не проблема: он может сколько угодно писать о самураях, космосе, пустоте, насекомых и оборотнях.

У него есть $$$n$$$ постоянных читателей, каждый из которых в $$$i$$$-й год прочитает один из $$$k_i$$$ романов, выпущенных Велепиным. Читатели очень любят обсуждать новинки, поэтому $$$j$$$-й из них будет доволен в течение года, если такой же роман, как и он, прочитают как минимум $$$a_j$$$ человек, включая его самого.

Издание, с которым подписал контракт Велепин, очень современно: у него есть возможность контролировать, какое произведение прочитает каждый из поклонников. Оно не хочет издавать романы просто так, поэтому хотя бы один экземпляр каждого романа должен попасть в руки читателя. Издание надеется выиграть награду «Издание $$$q$$$-летия», поэтому отдел маркетинга хочет узнать, какое максимальное количество постоянных читателей можно сделать довольными в течение каждого года, оптимально распределяя романы между ними. Так как в отделе маркетинга нет никого, кто мог бы это сделать, он обратился к вам за помощью.

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

В первой строке дано одно целое число $$$n$$$ $$$(2 \leqslant n \leqslant 300\,000)$$$ — количество постоянных читателей Велепина.

Во второй строке дано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leqslant a_j \leqslant n)$$$ — количество людей, которые должны читать тот же роман, что и $$$j$$$-й, чтобы он был доволен.

В третьей строке дано одно целое число $$$q$$$ ($$$1 \leqslant q \leqslant 300\,000$$$) — количество лет, которые нужно проанализировать.

В каждой из следующих $$$q$$$ строк дано по одному целому числу $$$k_i$$$ $$$(2 \leqslant k_i \leqslant n)$$$ — количество романов, которые Велепин должен написать в $$$i$$$-й год.

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

Выведите $$$q$$$ строк, в каждой из них ровно одно число — максимальное количество человек, которые могут быть довольны в $$$i$$$-й год, если Велепин выпустит $$$k_i$$$ романов.

Примеры

Входные данные
5
2 2 2 2 1
3
2
3
4
Выходные данные
5
5
3
Входные данные
6
1 2 3 4 5 6
2
2
3
Выходные данные
5
4
Входные данные
6
4 4 1 4 4 4
3
2
3
4
Выходные данные
6
5
1

Примечание

В первом примере в первый год оптимальным является разделение $$$1, 1, 1, 2, 2$$$ (первый роман читают первые три человека, а два последних — второй). Во второй год оптимальным решением является $$$1, 1, 2, 2, 3$$$ (первый роман читает первый и второй человек, второй роман читает третий и четвертый человек, третий роман читает пятый человек). В третий год оптимальным будет разбиение $$$1, 2, 2, 4, 3$$$. Соответственно количество довольных людей по годам будет $$$5, 5, 3$$$.

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

Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.

Доп. ограничения
ГруппаБаллы$$$n$$$$$$q$$$Необх. группыКомментарий
00Тесты из условия.
115$$$a_j \leqslant 2$$$
220$$$q = 1$$$$$$k_1 = 2$$$
320$$$n \le 100$$$$$$q \le 100$$$
425$$$n \le 100\,000$$$$$$q \le 10$$$
5200–4