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

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

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

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

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

В первой строке дано одно целое число $$$n$$$ $$$(2 \le n \le 3 \cdot 10^5)$$$ — количество постоянных читателей Велепина.

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

В третьей строке дано одно целое число $$$q$$$ $$$(1 \le q \le 3 \cdot 10^5)$$$ — количество лет, которые нужно проанализировать.

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

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

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

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

Во втором примере в первый год оптимальным является разделение $$$1, 1, 1, 1, 1, 2$$$, тогда будут довольны все кроме $$$6$$$-го человека. Во второй год оптимальным разделением является $$$1, 1, 1, 1, 2, 3$$$, тогда будут довольны все кроме $$$5$$$-го и $$$6$$$-го человека.