Знаменитый писатель Велепин очень продуктивен. Совсем недавно он подписал контракт с известным изданием, и теперь за $$$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$$$ | Необх. группы | Комментарий |
0 | 0 | – | – | – | Тесты из условия. |
1 | 15 | – | – | – | $$$a_j \leqslant 2$$$ |
2 | 20 | – | $$$q = 1$$$ | – | $$$k_1 = 2$$$ |
3 | 20 | $$$n \le 100$$$ | $$$q \le 100$$$ | – | |
4 | 25 | $$$n \le 100\,000$$$ | $$$q \le 10$$$ | – | |
5 | 20 | – | – | 0–4 |