Recently in Divanovo, a huge river locks system was built. There are now $n$ locks, the $i$-th of them has the volume of $v_i$ liters, so that it can contain any amount of water between $0$ and $v_i$ liters. Each lock has a pipe attached to it. When the pipe is open, $1$ liter of water enters the lock every second.

The locks system is built in a way to immediately transfer all water exceeding the volume of the lock $i$ to the lock $i + 1$. If the lock $i + 1$ is also full, water will be transferred further. Water exceeding the volume of the last lock pours out to the river.

The picture illustrates $5$ locks with two open pipes at locks $1$ and $3$. Because locks $1$, $3$, and $4$ are already filled, effectively the water goes to locks $2$ and $5$.

Note that the volume of the $i$-th lock may be greater than the volume of the $i + 1$-th lock.

To make all locks work, you need to completely fill each one of them. The mayor of Divanovo is interested in $q$ independent queries. For each query, suppose that initially all locks are empty and all pipes are closed. Then, some pipes are opened simultaneously. For the $j$-th query the mayor asks you to calculate the minimum number of pipes to open so that all locks are filled no later than after $t_j$ seconds.

Please help the mayor to solve this tricky problem and answer his queries.


-----Input-----

The first lines contains one integer $n$ ($1 \le n \le 200000$) — the number of locks.

The second lines contains $n$ integers $v_1, v_2, \dots, v_n$ ($1 \le v_i \le 10^9$)) — volumes of the locks.

The third line contains one integer $q$ ($1 \le q \le 200000$) — the number of queries.

Each of the next $q$ lines contains one integer $t_j$ ($1 \le t_j \le 10^9$) — the number of seconds you have to fill all the locks in the query $j$.


-----Output-----

Print $q$ integers. The $j$-th of them should be equal to the minimum number of pipes to turn on so that after $t_j$ seconds all of the locks are filled. If it is impossible to fill all of the locks in given time, print $-1$.


-----Examples-----

Input
5
4 1 5 4 1
6
1
6
2
3
4
5
Output
-1
3
-1
-1
4
3
Input
5
4 4 4 4 4
6
1
3
6
5
2
4
Output
-1
-1
4
4
-1
5


-----Note-----

There are $6$ queries in the first example test.

In the queries $1, 3, 4$ the answer is $-1$. We need to wait $4$ seconds to fill the first lock even if we open all the pipes.

In the sixth query we can open pipes in locks $1$, $3$, and $4$. After $4$ seconds the locks $1$ and $4$ are full. In the following $1$ second $1$ liter of water is transferred to the locks $2$ and $5$. The lock $3$ is filled by its own pipe.

Similarly, in the second query one can open pipes in locks $1$, $3$, and $4$.

In the fifth query one can open pipes $1, 2, 3, 4$.

Difficulty: HARD
Tags: Dynamic programming

Sorting

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Sorting

Greedy algorithms

Starter code:

Solutions:
import math
lines = [*open(0)]
sizes = lines[1].split(' ')
(tot, running) = (0, 0)
minval = 0
for lock in sizes:
	tot += int(lock)
	running += 1
	minval = max(minval, tot / running)
for mintime in lines[3:]:
	if int(mintime) < minval:
		print('-1')
	else:
		print(math.ceil(tot / int(mintime)))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	V = list(map(int, input().split()))
	arr = []
	curr = 0
	val = -float('inf')
	for i in range(n):
		curr += V[i]
		val = max(val, curr // (i + 1) + (curr % (i + 1) > 0) * 1)
		arr.append(val)
	S = sum(V)
	q = int(input())
	for _ in range(q):
		tj = int(input())
		cnt = S // tj + (S % tj > 0) * 1
		print(cnt) if cnt <= n and arr[cnt - 1] <= tj else print(-1)
	return
solve()


from math import ceil
import os, sys
isLocal = os.environ.get('USER', '') == 'xueenpeng'
if isLocal:
	sys.stdin = open('./file/input.txt', 'r')
	pass

def main():
	n = int(input())
	locks = list(map(int, input().split(' ')))
	q = int(input())
	querys = []
	for _ in range(q):
		querys.append(int(input()))
	minTime = 0
	count = 0
	total = 0
	for lock in locks:
		count += 1
		total += lock
		minTime = max(minTime, ceil(total / count))
	for query in querys:
		if query < minTime:
			print(-1)
		else:
			ans = ceil(total / query)
			print(ans)
main()


import itertools
n = int(input())
v = list(itertools.accumulate(map(int, input().split())))
m = max(((v[i] - 1) // (i + 1) + 1 for i in range(n)))
for _ in range(int(input())):
	t = int(input())
	print((v[-1] - 1) // t + 1 if t >= m else -1)


import sys
n = int(input())
V = [int(i) for i in input().split()]
(time, total) = (0, 0)
for i in range(n):
	total += V[i]
	time = max(time, (total + i) // (i + 1))
	pass
for q in range(int(input())):
	t = int(input())
	if t < time:
		res = -1
	else:
		res = (total + t - 1) // t
	sys.stdout.write(str(res) + '\n')
	pass


n = int(input())
V = [int(i) for i in input().split()]
(time, total) = (0, 0)
for i in range(n):
	total += V[i]
	time = max(time, (total + i) // (i + 1))
	pass
for q in range(int(input())):
	t = int(input())
	if t < time:
		print(-1)
	else:
		print((total + t - 1) // t)
	pass


import math
from itertools import accumulate

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	qn = int(input())
	acc = list(accumulate(arr))
	cca = [0] * len(acc)
	for i in range(len(acc)):
		cca[i] = int(math.ceil(acc[i] / (i + 1)))
	maxx = max(cca)
	for _ in range(qn):
		q = int(input())
		if q < maxx:
			print(-1)
		else:
			print(int(math.ceil(acc[-1] / q)))

def init():
	import os
	import sys
	sys.setrecursionlimit(2 * 10 ** 6)
	if 'CP_LOCAL_ENV' in os.environ:
		sys.stdin = open('cf_test_d.txt')
init()
main()


from math import ceil
r = range
i = lambda : int(input())
s = lambda : input().split()
for _ in r(1):
	n = i()
	v = list(map(int, s()))
	dp = []
	sum = 0
	max = 0
	for _ in r(n):
		sum += v[_]
		val = ceil(sum / (_ + 1))
		dp += (val,)
		if val > max:
			max = val
	for _ in r(i()):
		t = i()
		print(ceil(sum / t)) if max <= t else print(-1)


from math import ceil
n = int(input())
v = list(map(int, input().split()))
s = sum(v)
prefix = [0]
for i in range(n):
	prefix.append(prefix[i] + v[i])
min_time = max([ceil(prefix[i] / i) for i in range(1, n + 1)])
q = int(input())
for _ in range(q):
	t = int(input())
	if t < min_time:
		print(-1)
	else:
		print(ceil(s / t))


import math
n = int(input())
arr = list(map(int, input().split()))
sum = 0
maxi = 0
for i in range(n):
	sum += arr[i]
	maxi = max(maxi, math.ceil(sum / (i + 1)))
for _ in range(int(input())):
	t = int(input())
	ans = math.ceil(sum / t)
	if maxi > t:
		ans = -1
	print(int(ans))


import math as ma
r = range
R = lambda : int(input())
num_of_locks = R()
vols_arr = list(map(int, input().split(' ')))
sum_of_vols = 0
avg_vols = []
for _ in r(len(vols_arr)):
	sum_of_vols += vols_arr[_]
	avg_vols += (ma.ceil(sum_of_vols / (_ + 1)),)
max_avg_vols = max(avg_vols)
for _ in r(R()):
	liters = R()
	answer = ma.ceil(sum_of_vols / liters)
	if max_avg_vols > liters:
		answer = -1
	print(answer)


def ceil_div(a, b):
	return (a - 1) // b + 1
n = int(input())
v = list(map(int, input().split()))
p_v = [0]
for v_i in v:
	p_v.append(p_v[-1] + v_i)
m = max((ceil_div(p_v[i], i) for i in range(1, n + 1)))
q = int(input())
for _ in range(q):
	t_j = int(input())
	if t_j < m:
		print(-1)
	else:
		print(ceil_div(p_v[n], t_j))


import math
for _ in range(1):
	n = int(input())
	a = list(map(int, input().split()))
	maxi = [0] * n
	s = 0
	for i in range(n):
		s += a[i]
		maxi[i] = max(maxi[i - 1], math.ceil(s / (i + 1)))
	q = int(input())
	for i in range(q):
		t = int(input())
		ans = math.ceil(s / t)
		if ans <= n and t >= maxi[ans - 1]:
			print(ans)
		else:
			print(-1)


import math
n = int(input())
L = list(map(int, input().split()))
P = [0] * n
P[0] = L[0]
for i in range(1, n):
	P[i] = P[i - 1] + L[i]
m = L[0]
for i in range(1, n):
	a = P[i]
	b = math.ceil(a / (i + 1))
	if b > m:
		m = b
	else:
		pass
q = int(input())
for _ in range(q):
	s = int(input())
	if s < m:
		print(-1)
	else:
		a = P[-1]
		print(math.ceil(a / s))


import bisect
import itertools
n = int(input())
v = list(itertools.accumulate(map(int, input().split())))
t = list(itertools.accumulate(((v[i] - 1) // (i + 1) + 1 for i in range(n)), max))
t = list((max(t[i], (v[-1] - 1) // (i + 1) + 1) for i in range(n)))
t.reverse()
for _ in range(int(input())):
	a = bisect.bisect_right(t, int(input()))
	print(n + 1 - a if a > 0 else -1)


n = int(input())
v = list(map(int, input().split()))
assert n == len(v)
vs = v[0]
ts = [0] * n
ts[0] = v[0]
for i in range(1, n):
	vs += v[i]
	ts[i] = max(ts[i - 1], (vs + i + 1 - 1) // (i + 1))
q = int(input())
for i in range(q):
	t = int(input())
	if t < ts[-1]:
		print(-1)
	else:
		print((vs + t - 1) // t)


n = int(input())
v = list(map(int, input().split()))
q = int(input())
sm = sum(v)
pr = v[0]
t = [sm]
smp = v[0]
for i in range(1, n):
	smp += v[i]
	pr = max(pr, pr + (smp - pr * (i + 1) + i) // (i + 1))
	t += [max(pr, pr + (sm - (i + 1) * pr + i) // (i + 1))]
for _ in range(q):
	ta = int(input())
	if ta < t[-1]:
		print(-1)
	else:
		print((sm + ta - 1) // ta)


import bisect

def solve():
	(a,) = list(map(int, input().split()))
	mas = list(map(int, input().split()))
	vents = []
	prefsum = [0]
	for i in range(len(mas)):
		prefsum.append(prefsum[-1] + mas[i])
	ourmax = 0
	for i in range(len(mas)):
		ourmax = max(ourmax, (prefsum[i + 1] + i) // (i + 1))
		vents.append(-max((prefsum[-1] + i) // (i + 1), ourmax))
	q = int(input())
	for i in range(q):
		request = int(input())
		x = bisect.bisect_left(vents, -request)
		if x == a:
			print(-1)
		else:
			print(x + 1)
n = 1
while n != 0:
	n -= 1
	solve()


import itertools
import bisect
n = int(input())
v = list(map(int, input().split()))
s = list(itertools.accumulate(v))
u = [(s[i] - 1) // (i + 1) + 1 for i in range(n)]
k = list(itertools.accumulate(u, max))
t = [float('inf'), s[n - 1]] + [max(k[i - 2], (s[n - 1] - 1) // i + 1) for i in range(2, n + 1)]
t.reverse()
for _ in range(int(input())):
	a = bisect.bisect_right(t, int(input()))
	print(n + 1 - a if a > 0 else -1)


from math import ceil as cl
n = int(input())
lst = list(map(int, input().split(' ')))
mx = -1
sum = 0
for i in range(n):
	sum += lst[i]
	mx = max(mx, cl(sum / (i + 1)))
q = int(input())
for y in range(q):
	h = int(input())
	ans = cl(sum / h)
	if mx > h:
		ans = -1
	print(ans)


num_locks = int(input())
volumn = list(map(int, input().split()))
sum_cur = 0
min_t = []
max_min_t = []
for i in range(len(volumn)):
	sum_cur += volumn[i]
	t_i = sum_cur // (i + 1) + (sum_cur % (i + 1) > 0) * 1
	min_t.append(t_i)
	if i == 0:
		max_min_t.append(t_i)
	else:
		max_min_t.append(max(max_min_t[-1], t_i))
num_queries = int(input())
sv = sum(volumn)
for _ in range(num_queries):
	t = int(input())
	min_open = sv // t + (sv % t > 0) * 1
	if min_open > num_locks:
		print(-1)
	elif t < max_min_t[min_open - 1]:
		print(-1)
	else:
		print(min_open)