Недавно в Диваново построили огромную шлюзовую систему. Всего было построено \(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\) секунд все шлюзы стали заполнены.
Помогите мэру справиться с этой сложной задачей, и ответьте на все его запросы!
Выходные данные
Выведите \(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
|