Недавно в Диваново построили огромную шлюзовую систему. Всего было построено $$$n$$$ шлюзов, $$$i$$$-й из них имеет объем $$$v_i$$$ литров. Изначально все шлюзы пусты. В каждый шлюз ведет труба, при открытии которой в шлюз будет поступать по $$$1$$$ литру воды в секунду. Исходно все трубы закрыты.
Шлюзовая система устроена так, что если доливать воду в $$$i$$$-й шлюз сверх его объема, она будет моментально моментально переливаться в шлюз с номером $$$i + 1$$$. Если шлюз c номером $$$i + 1$$$ тоже заполнен, вода будет переливаться дальше. Вода из последнего шлюза будет выливаться в озеро.
Рисунок показывает $$$5$$$ шлюзов с открытыми трубами к шлюзам $$$1$$$ и $$$3$$$. Так как шлюзы $$$1$$$, $$$3$$$ и $$$4$$$ уже заполнены, фактически вода идет в шлюзы $$$2$$$ и $$$5$$$.
Для того, чтобы шлюзы начали функционировать, необходимо заполнить каждый из них. Мэра Дивановской области интересует $$$q$$$ независимых запросов. Для каждого запроса предположим, что изначально все шлюзы пусты и все трубы закрыты, затем одновременно открываются несколько труб. Для $$$j$$$-го запроса мэр хочет знать, какое минимальное число труб надо включить, чтобы не позже чем через $$$t_j$$$ секунд все шлюзы стали заполнены.
Помогите мэру справиться с этой сложной задачей и ответьте на все его запросы!
В первой строке вводится одно целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — количество шлюзов.
Во второй строке вводятся $$$n$$$ целых чисел $$$v_1, v_2, \dots, v_n$$$ ($$$1 \le v_i \le 10^9$$$) — объемы шлюзов.
В третьей строке вводится одно целое число $$$q$$$ ($$$1 \le q \le 200\,000$$$) — число запросов.
В следующих $$$q$$$ строках вводится по одному целому числу $$$t_i$$$ ($$$1 \le t_j \le 10^9$$$) — время, за которое нужно наполнить все шлюзы в $$$j$$$-м запросе.
Выведите $$$q$$$ чисел, $$$j$$$-е из них должно быть равно минимальному числу труб, которое нужно открыть, чтобы наполнить все шлюзы за время $$$t_j$$$. Если за это время наполнить всю шлюзы невозможно, выведите $$$-1$$$.
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | |||||||
| Группа | Баллы | $$$n$$$ | $$$q$$$ | $$$v_i$$$ | $$$t_j$$$ | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | – | Тесты из условия. |
| 1 | 17 | $$$n \le 50$$$ | $$$q \le 50$$$ | $$$v_i \le 100$$$ | $$$t_j \le 100$$$ | 0 | |
| 2 | 14 | – | – | – | – | – | Все $$$v_i$$$ равны. |
| 3 | 19 | $$$n \le 300$$$ | $$$q \le 300$$$ | – | – | 0, 1 | |
| 4 | 24 | $$$n \le 5000$$$ | $$$q \le 5000$$$ | – | – | 0, 1, 3 | |
| 5 | 26 | – | – | – | – | 0 – 4 | |
5 4 1 5 4 1 6 1 6 2 3 4 5
-1 3 -1 -1 4 3
5 4 4 4 4 4 6 1 3 6 5 2 4
-1 -1 4 4 -1 5
В первом примере $$$6$$$ запросов:
В запросах $$$1, 3, 4$$$ ответ $$$-1$$$. Чтобы заполнить первый шлюз нужно подождать $$$4$$$ секунды, даже если открыты все трубы.
В шестом запросе можно открыть трубы в шлюзах $$$1, 3$$$, и $$$4$$$. Тогда через $$$4$$$ секунды заполнятся шлюзы $$$1$$$ и $$$4$$$. Через $$$1$$$ секунду $$$1$$$ литр воды перельётся в шлюзы $$$2$$$ и $$$5$$$. Шлюз $$$3$$$ будет заполнен своей трубой.
Аналогично во втором запросе можно открыть трубы в шлюзах $$$1, 3$$$ и $$$4$$$.
В пятом запросе можно открыть трубы в шлюзах с номерами $$$1, 2, 3, 4$$$.
