Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.
Недавно в Диваново построили огромную шлюзовую систему. Всего было построено \(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\).
В первом примере \(6\) запросов:
В запросах \(1, 3, 4\) ответ \(-1\). Чтобы заполнить первый шлюз нужно подождать \(4\) секунды, даже если открыты все трубы.
В шестом запросе можно открыть трубы в шлюзах \(1, 3\), и \(4\). Тогда через \(4\) секунды заполнятся шлюзы \(1\) и \(4\). Через \(1\) секунду \(1\) литр воды перельётся в шлюзы \(2\) и \(5\). Шлюз \(3\) будет заполнен своей трубой.
Аналогично во втором запросе можно открыть трубы в шлюзах \(1, 3\) и \(4\).
В пятом запросе можно открыть трубы в шлюзах с номерами \(1, 2, 3, 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 1 5 4 1
6
1
6
2
3
4
5
|
-1
3
-1
-1
4
3
|
|
2
|
5
4 4 4 4 4
6
1
3
6
5
2
4
|
-1
-1
4
4
-1
5
|