| Codeforces Round 802 (Div. 2) |
|---|
| Закончено |
Недавно в Диваново построили огромную шлюзовую систему. Всего было построено $$$n$$$ шлюзов, $$$i$$$-й из них имеет объем $$$v_i$$$ литров, то есть в любой момент времени в нем может находиться любой объем воды от $$$0$$$ до $$$v_i$$$ литров. В каждый шлюз ведет труба, при открытии которой в шлюз будет поступать по $$$1$$$ литру воды в секунду.
Шлюзовая система устроена так, что если доливать воду в $$$i$$$-й шлюз сверх его объема, то он будет моментально передавать всю лишнюю воду шлюзу с номером $$$i + 1$$$. Если шлюз c номером $$$i + 1$$$ тоже станет заполнен, то вся лишняя вода будет переливаться дальше. Вода из последнего шлюза будет выливаться в реку.
Рисунок показывает $$$5$$$ шлюзов с открытыми трубами к шлюзам $$$1$$$ и $$$3$$$. Так как шлюзы $$$1$$$, $$$3$$$ и $$$4$$$ уже заполнены, фактически вода идет в шлюзы $$$2$$$ и $$$5$$$. Обратите внимание, что объем $$$i$$$-го шлюза может быть больше объема $$$i + 1$$$-го шлюза.
Для того, чтобы шлюзы начали функционировать, необходимо заполнить каждый из них. Мэра Дивановской области интересует $$$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_j$$$ ($$$1 \le t_j \le 10^9$$$) — время, за которое нужно наполнить все шлюзы в $$$j$$$-м запросе.
Выведите $$$q$$$ чисел. $$$j$$$-е из них должно быть равно минимальному числу труб, которые придётся открыть, чтобы наполнить все шлюзы за время $$$t_j$$$. Если за это время наполнить всю шлюзы невозможно, то выведите $$$-1$$$.
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$$$.
