Chef has an array A of N positive integers. Chef can perform the following operation any (possibly zero) number of times on the array.

Choose any index i such that (1 < i ≤ N);
Choose an integer X such that (1≤ X ≤ A_{i});
Set A_{(i-1)} := A_{(i-1)} + X;
Set A_{i} := A_{i} - X.

Help Chef to minimize the maximum value of array A using the above operations .

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer N, the size of array A.
- The second line of each test case contains N space-seperated integers, the elements of array A.

------ Output Format ------ 

For each test case, output on a new line, the minimized maximum value possible of array A.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
3
4
1 5 7 6
3
5 15 19
4
10 3 5 7

----- Sample Output 1 ------ 
5
13
10
----- explanation 1 ------ 
Test case $1$: Consider the following $3$ operations on the array.
- Choose $i = 3$ and $X = 4$. Here $X ≤ A_{3}$. After operation, the array becomes $[1,9,3,6]$.
- Choose $i = 2$ and $X = 4$. Here $X ≤ A_{2}$. After operation, the array becomes $[5,5,3,6]$.
- Choose $i = 4$ and $X = 1$. Here $X ≤ A_{4}$. After operation, the array becomes $[5,5,4,5]$.

So the minimum value of maximum element of array is $5$.

Test case $2$: Consider the following $2$ operations on the array.
- Choose $i = 2$ and $X = 8$. Here $X ≤ A_{2}$. After operation, the array becomes $[13, 7, 19]$.
- Choose $i = 3$ and $X = 6$. Here $X ≤ A_{3}$. After operation, the array becomes $[13, 13, 13]$.

So the minimum value of maximum element of array is $5$.

Test case $3$: We cannot make $A_{1}$ less than $10$ using any number of operations. Thus, the minimum value of maximum element is $10$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Range queries

Complete search


Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(max([-(-sum(a[:i + 1]) // (i + 1)) for (i, e) in enumerate(a)]))


def dropdigit(alist):
	y = alist.pop()
	return y

def checklist(mylist):
	if mylist[-1] < -(-sum(mylist) // len(mylist)):
		y = dropdigit(mylist)
		checklist(mylist)
	return max(-(-sum(mylist) // len(mylist)), mylist[0])
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	tot = sum(a)
	cumavg = [-(-sum(a[:i + 1]) // (i + 1)) for (i, e) in enumerate(a)]
	res = checklist(a)
	print(max(cumavg))


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	temp = 0
	for j in range(n):
		ans = max(ans, math.ceil((temp + a[j]) / (j + 1)))
		temp += a[j]
	print(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	(N, sm, av) = (inp(), 0, 0)
	for (i, a) in enumerate(invr(), start=1):
		sm += a
		tmp = -(-sm // i)
		if av < tmp:
			av = tmp
	ans.append(av)
outplt(ans)


t = int(input())
for _ in range(t):
	N = int(input())
	arr = list(map(int, input().strip().split()))
	mx = -1
	sm = sum(arr)
	for i in range(N - 1, 0, -1):
		cll = (sm + i) // (i + 1)
		if cll < arr[i]:
			d = arr[i] - cll
			arr[i] = cll
			arr[i - 1] += d
			sm -= cll
		else:
			sm -= arr[i]
		mx = max(arr[i], mx)
	mx = max(mx, arr[0])
	print(mx)


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


import math
t = int(input())
for _ in range(t):
	n = int(input())
	vals = input().split(' ')
	cur_max = -1
	cur_sum = 0
	ans = -1
	for i in range(n):
		cur_sum += int(vals[i])
		cur_ans = math.ceil(cur_sum / (i + 1))
		if cur_ans > ans:
			ans = cur_ans
	print(ans)


import math
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	agg = 0
	ans = 0
	for i in range(n):
		agg += a[i]
		ans = max(ans, math.ceil(agg / (i + 1)))
	print(ans)


def f(arr):
	m = arr[0]
	count = 0
	for i in range(1, len(arr)):
		val = arr[i]
		if val <= m:
			count += m - val
		elif val - m <= count:
			count -= val - m
		else:
			val -= count
			ex = val - m
			cols = i + 1
			if ex % cols == 0:
				m += ex // cols
				count = 0
			else:
				m += ex // cols + 1
				count = cols - ex % cols
	return m
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(el) for el in input().split(' ')]
	print(f(arr))


import math
n = int(input())
for i in range(n):
	m = int(input())
	l = [int(j) for j in input().split()]
	l1 = [0] * len(l)
	sum = 0
	for i in range(len(l)):
		sum += l[i]
		l1[i] = math.ceil(sum / (i + 1))
	print(max(l1))


import math
t = int(input())
for t in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = l[0]
	sum = l[0]
	for i in range(1, len(l)):
		sum += l[i]
		ans = max(ans, math.ceil(sum / (i + 1)))
	print(ans)


n = int(input())
import math
for i in range(n):
	n = int(input())
	ins = list(map(int, input().split(' ')))
	x = y = ins[0]
	for i in range(1, n):
		x += ins[i]
		y = max(y, math.floor((x + i) / (i + 1)))
	print(y)


a = int(input())
for i in range(a):
	N = int(input())
	A = list(map(int, input().split()))
	t = sum(A)
	x = t / N
	y = 0
	p = 0
	B = []
	for j in range(N):
		y += A[j]
		if y / (j + 1) > x:
			if y % (j + 1) != 0:
				s = y // (j + 1) + 1
			else:
				s = y // (j + 1)
			B.append(s)
		else:
			p += 1
	if p == N:
		if t % N != 0:
			ans = t // N + 1
		else:
			ans = t // N
		print(ans)
	else:
		print(max(B))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = pref = 0
	for i in range(n):
		pref += a[i]
		ans = max(ans, (pref + i) // (i + 1))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	A = [int(x) for x in input().split()]
	(res, prefSum) = (0, 0)
	for i in range(n):
		prefSum += A[i]
		res = max((prefSum + i) // (i + 1), res)
	print(res)


import math
for i in range(int(input())):
	xxxx = int(input())
	l = list(map(int, input().split()))
	ans = l[0]
	su = l[0]
	for i in range(1, len(l)):
		su += l[i]
		ans = max(ans, math.ceil(su / (i + 1)))
	print(ans)


import math
t = int(input())
while t:
	n = int(input())
	arr = [int(i) for i in input().split()]
	sum = arr[0]
	m = arr[0]
	for i in range(1, n):
		sum += arr[i]
		m = max(m, math.ceil(sum / (i + 1)))
	print(m)
	t -= 1


from collections import defaultdict
import math
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	csum = 0
	mx = -1
	for i in range(n):
		csum += a[i]
		mx = max(math.ceil(csum / (i + 1)), mx)
	print(mx)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = arr[0]
	sm = arr[0]
	for i in range(1, n):
		sm += arr[i]
		temp = (sm + i) // (i + 1)
		ans = max(ans, temp)
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(s, res) = (arr[0], arr[0])
	for i in range(1, n):
		s += arr[i]
		res = max(res, math.ceil(s / (i + 1)))
	print(res)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	(sm, ans) = (lst[0], lst[0])
	for i in range(1, n):
		sm += lst[i]
		ans = max(ans, (sm + i) // (i + 1))
	print(ans)


import math
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	prefix = 0
	ans = 0
	for i in range(n):
		prefix = prefix + a[i]
		avg = math.ceil(prefix / (i + 1))
		ans = max(avg, ans)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = ps = 0
	for i in range(n):
		ps += l[i]
		ans = max(ans, (ps + i) // (i + 1))
	print(ans)


import math
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	res = sm = A[0]
	for i in range(1, N):
		sm += A[i]
		res = max(res, math.floor((sm + i) / (i + 1)))
	print(res)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	maxi = max(a)
	if maxi == a[0]:
		print(a[0])
	else:
		b = []
		for i in range(1, n + 1):
			b.append(math.ceil(sum(a[:i]) / i))
		print(max(b))


import math
case = int(input())
for i in range(case):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	maxn = -1
	csum = 0
	j = 0
	while j < n:
		csum += arr[j]
		if maxn <= arr[j]:
			div = csum // (j + 1)
			if div * (j + 1) == csum:
				maxn = max(maxn, div)
			else:
				maxn = max(maxn, div + 1)
		j += 1
	print(maxn)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(sum, res) = (0, 0)
	for i in range(n):
		sum += a[i]
		res = max(res, (sum + i) / (i + 1))
	print(int(res))


import sys
from typing import List

def is_valid_mid(n: int, ds: List[int], mid: int) -> bool:
	temp_vec = ds.copy()
	if temp_vec[0] > mid:
		return False
	for i in range(1, n):
		if temp_vec[i - 1] < mid:
			temp_vec[i] = temp_vec[i] - (mid - temp_vec[i - 1])
			temp_vec[i - 1] = mid
		if temp_vec[i] > mid:
			return False
	if max(temp_vec) > mid:
		return False
	return True

def play():
	num_of_elements = int(input())
	elements = list(map(int, input().split()))
	start = 0
	end = max(elements)
	ans = 1000000000
	while start <= end:
		mid = (start + end) // 2
		if is_valid_mid(num_of_elements, elements, mid):
			ans = min(ans, mid)
			end = mid - 1
		else:
			start = mid + 1
	print(ans)
num_of_tests = int(input())
for i in range(num_of_tests):
	play()


def func(n, arr, mid):
	arr1 = []
	for i in arr:
		arr1.append(i)
	if arr1[0] > mid:
		return False
	for i in range(1, n):
		if arr1[i - 1] < mid:
			arr1[i] = arr1[i] - (mid - arr1[i - 1])
			arr1[i - 1] = mid
		if arr1[i] > mid:
			return False
	if max(arr1) > mid:
		return False
	else:
		return True
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	ans = 1000000000.0
	max_element = max(arr)
	while i <= max_element:
		mid = i + (max_element - i) // 2
		if func(n, arr, mid):
			ans = min(ans, mid)
			max_element = mid - 1
		else:
			i = mid + 1
	print(ans)


def solve(n, arr, mid):
	newArray = arr.copy()
	if newArray[0] > mid:
		return False
	for i in range(1, n):
		if newArray[i - 1] < mid:
			buffer = mid - newArray[i - 1]
			newArray[i - 1] = mid
			newArray[i] = newArray[i] - buffer
		if newArray[i] > mid:
			return False
	maxElem = max(newArray)
	if maxElem > mid:
		return False
	return True
t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	j = max(arr)
	ans = int(2 ** 63 - 1)
	while i <= j:
		mid = int(i + (j - i) / 2)
		if solve(n, arr, mid):
			ans = min(ans, mid)
			j = mid - 1
		else:
			i = mid + 1
	print(ans)


def funn(a, b):
	if a < b:
		return True
	else:
		return False

def decode(n, thaar_r, madh):
	thaar = []
	thaar += thaar_r
	if thaar[0] > madh:
		return False
	for i in range(1, n):
		if funn(thaar[i - 1], madh):
			thaar[i] = thaar_r[i] + (thaar[i - 1] - madh)
			thaar[i - 1] = madh
		if thaar[i] > madh:
			return False
	if max(thaar) <= madh:
		return True
	return False
_ = int(input())
while _:
	n = int(input())
	haar = list(map(int, input().split()))
	i = 0
	j = max(haar)
	RESS = 1000000000.0
	while i <= j:
		madh = (i + j) // 2
		if decode(n, haar, madh):
			RESS = min(RESS, madh)
			j = madh - 1
		else:
			i = madh + 1
	print(int(RESS))
	_ -= 1


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	pre = []
	preavg = []
	s = 0
	avg = 0
	for i in arr:
		s += i
		pre.append(s)
	for i in range(len(pre)):
		avg = math.ceil(pre[i] / (i + 1))
		preavg.append(avg)
	print(max(preavg))


def get():
	return list(map(int, input().split()))

def avg(arr1):
	s = sum(arr1)
	n = len(arr1)
	a = s // n
	if s % n == 0:
		return a
	else:
		return a + 1
t = int(input())
while t > 0:
	n = int(input())
	arr1 = list(get())
	arr2 = []
	for i in range(1, n + 1):
		arr2.append(avg(arr1[:i]))
	print(max(arr2))
	t = t - 1


def dec(n, l, m):
	l1 = []
	l1 += l
	if l1[0] > m:
		return False
	for i in range(1, n):
		if l1[i - 1] < m:
			l1[i] = l[i] + (l1[i - 1] - m)
			l1[i - 1] = m
		if l1[i] > m:
			return False
	if max(l1) <= m:
		return True
	return False
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	j = max(l)
	res = 1000000000.0
	while i <= j:
		m = (i + j) // 2
		if dec(n, l, m):
			res = min(res, m)
			j = m - 1
		else:
			i = m + 1
	print(int(res))
	t -= 1


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	lowest = min(a)
	highest = max(a)
	ans = highest
	while lowest <= highest:
		mid = (lowest + highest) // 2
		flag = 0
		b = a[:]
		i = n - 1
		while i > 0:
			if b[i] > mid:
				f = b[i] - mid
				b[i - 1] = b[i - 1] + f
				b[i] = b[i] - f
			i -= 1
		if max(b) > mid:
			lowest = mid + 1
		else:
			ans = min(ans, max(b))
			highest = mid - 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = max(l)
	high = max(l)
	low = min(l)
	while low <= high:
		l1 = [i for i in l]
		mid = (low + high) // 2
		for i in reversed(range(1, n)):
			if l1[i] > mid:
				l1[i - 1] += l1[i] - mid
				l1[i] = mid
		c = max(l1)
		if c > mid:
			low = mid + 1
		else:
			a = min(a, c)
			high = mid - 1
	print(a)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	low = min(l)
	high = max(l)
	res = high
	maxi = high
	while low <= high:
		mid = (low + high) // 2
		c = 0
		m = []
		m.extend(l)
		for i in range(n - 1, 0, -1):
			if m[i] > mid:
				m[i - 1] += m[i] - mid
				m[i] = mid
		d = max(m)
		maxi = min(maxi, d)
		if maxi > mid:
			low = mid + 1
		else:
			res = min(res, maxi)
			high = mid - 1
	print(res)


from sys import stdin, stdout
read = stdin.readline
from math import floor, ceil

def splitter(L):
	ans = [[L[0]]]
	for i in range(1, len(L)):
		if L[i] < L[i - 1]:
			ans += [[]]
		ans[-1] += [L[i]]
	return ans

def equalize(L):
	avg = sum(L) / len(L)
	ceilCount = sum(L) - len(L) * floor(avg)
	return [floor(avg)] * (len(L) - ceilCount) + [ceil(avg)] * ceilCount

def alpha(L):
	ans = []
	for i in splitter(L):
		ans.append(equalize(i))
	didSomething = 1
	while didSomething and len(ans) > 1:
		for i in range(1, len(ans)):
			if min(ans[i]) >= max(ans[i - 1]):
				ans = ans[:i - 1] + [equalize(ans[i] + ans[i - 1])] + ans[i + 1:]
				break
			if i == len(ans) - 1:
				didSomething = 0
				break
	return ans

def sol(x):
	print(max([max(i) for i in alpha(x)]))
tt = read().strip()
tt = int(tt)
for _ in range(tt):
	read()
	x = list(map(int, read().split()))
	sol(x)


t = int(input())
for u in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = a[0]
	c = 1
	m = []
	l = []
	for i in range(0, n - 1):
		if a[i + 1] >= a[i]:
			s += a[i + 1]
			c += 1
		else:
			l.append(s)
			m.append(c)
			s = a[i + 1]
			c = 1
	l.append(s)
	m.append(c)
	z = True
	while z:
		z = False
		x = []
		y = []
		s = l[0]
		c = m[0]
		p = s / c
		for j in range(1, len(l)):
			av = l[j] / m[j]
			if av >= p:
				s += l[j]
				c += m[j]
				p = s / c
				z = True
			else:
				x.append(s)
				y.append(c)
				s = l[j]
				c = m[j]
		x.append(s)
		y.append(c)
		(l, m) = (x, y)
	print(l[0] // m[0] + bool(l[0] % m[0]))


import sys

def is_valid_mid(arr, mid):
	n = len(arr)
	if arr[0] > mid:
		return False
	for j in range(1, n):
		if arr[j - 1] < mid:
			arr[j] = arr[j] - (mid - arr[j - 1])
			arr[j - 1] = mid
		if arr[j] > mid:
			return False
	mx = max(arr)
	if mx > mid:
		return False
	return True

def binary_search(arr):
	i = 0
	j = max(arr)
	ans = sys.maxsize
	while i <= j:
		mid = i + (j - i) // 2
		if is_valid_mid(arr.copy(), mid):
			ans = min(ans, mid)
			j = mid - 1
		else:
			i = mid + 1
	return ans
t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	print(binary_search(arr))


from math import ceil
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	highest_max = 0
	total = 0
	for i in range(n):
		total += a[i]
		cur_av = ceil(total / (i + 1))
		if cur_av > highest_max:
			highest_max = cur_av
	print(highest_max)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	for i in range(1, n + 1):
		b = a[:i]
		l.append(math.ceil(sum(b) / len(b)))
	print(max(l))


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	b = max(a)
	c = min(a)
	d = b
	while c <= b:
		e = (b + c) // 2
		f = 0
		g = a.copy()
		for i in reversed(range(1, n)):
			if g[i] > e:
				g[i - 1] += g[i] - e
				g[i] = e
		h = max(g)
		if h > e:
			c = e + 1
		else:
			d = min(d, h)
			b = e - 1
	print(d)


def Keshu(A):
	s = sum(A)
	n = len(A)
	if s % n == 0:
		return s // n
	else:
		return s // n + 1
t = int(input())
for i in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	B = []
	for i in range(1, n + 1):
		B.append(Keshu(A[:i]))
	print(max(B))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(low, high) = (min(l), max(l))
	result = high
	while low <= high:
		new_l = list(l)
		mid = (low + high) // 2
		for i in range(-1, n * -1, -1):
			if new_l[i] > mid:
				new_l[i - 1] += new_l[i] - mid
				new_l[i] = mid
		if mid == max(new_l):
			result = max(new_l)
			high = mid - 1
		else:
			low = mid + 1
	print(result)


for i in range(int(input())):

	def check(n, a, m):
		b = a.copy()
		if b[0] > m:
			return False
		for j in range(1, n):
			if b[j - 1] < m:
				temp = m - b[j - 1]
				b[j - 1] = m
				b[j] -= temp
			if b[j] > m:
				return False
		x = max(b)
		if x > m:
			return False
		return True
	n = int(input())
	s = input()
	a = [int(i) for i in s.split()]
	x = 0
	y = max(a)
	ans = y
	while x <= y:
		m = x + (y - x) // 2
		if check(n, a, m):
			ans = min(ans, m)
			y = m - 1
		else:
			x = m + 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	maxval = 0
	total = 0
	count = 0
	for i in a:
		total += i
		count += 1
		if total % count == 0:
			mv = total // count
		else:
			mv = total // count + 1
		if mv > maxval:
			maxval = mv
	print(maxval)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	presum = []
	preavg = []
	s = 0
	avg = 0
	for i in a:
		s += i
		presum.append(s)
	for j in range(len(presum)):
		avg = math.ceil(presum[j] / (j + 1))
		preavg.append(avg)
	print(max(preavg))


import math
import itertools

def minimizeArrayValue(nums):
	nums = list(itertools.accumulate(nums))
	return max(((i + nums[i]) // (1 + i) for i in range(len(nums))))
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(minimizeArrayValue(arr))


def avg(a):
	s = sum(a)
	n = len(a)
	if s % n == 0:
		return s // n
	else:
		return s // n + 1
for _ in range(int(input())):
	m = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in range(1, m + 1):
		b.append(avg(a[:i]))
	print(max(b))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(l, h, res) = (0, max(arr), max(arr))
	while l <= h:
		mid = (l + h) // 2
		temp = arr[:]
		for i in range(n - 1, 0, -1):
			if temp[i] > mid:
				temp[i - 1] += temp[i] - mid
		if temp[0] <= mid:
			h = mid - 1
			res = mid
		else:
			l = mid + 1
	print(res)


import math
t = int(input())
while t:
	n = int(input())
	arr = [int(x) for x in input().split()]
	avg = []
	for i in range(1, n + 1):
		s = sum(arr[0:i])
		mean = math.ceil(s / i)
		avg.append(mean)
	print(max(avg))
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = min(a)
	h = max(a)
	c = h
	while l <= h:
		b = a.copy()
		mid = int((l + h) / 2)
		for j in range(n - 1, 0, -1):
			if b[j] > mid:
				b[j - 1] += b[j] - mid
				b[j] = mid
		hn = max(b)
		if hn > mid:
			l = mid + 1
		else:
			c = min(h, hn)
			h = mid - 1
	print(int(c))


from math import ceil
from itertools import accumulate
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	nums = list(accumulate(arr))
	m = 0
	for (i, v) in enumerate(nums):
		diff = (i + v) // (i + 1)
		m = max(diff, m)
	print(m)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(l, h) = (min(a), max(a))
	ans = 1000000000000
	while l <= h:
		m = (l + h) // 2
		b = a.copy()
		for i in range(n - 1, 0, -1):
			if b[i] > m:
				b[i - 1] += b[i] - m
				b[i] = m
		mx = max(b)
		if mx > m:
			l = m + 1
		else:
			ans = min(ans, mx)
			h = m - 1
	print(ans)


from math import ceil
from itertools import accumulate
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	nums = list(accumulate(arr))
	m = max(((i + nums[i]) // (1 + i) for i in range(len(nums))))
	print(m)


import sys
from typing import List

def modeee(n: int, ds: List[int], mid: int) -> bool:
	vec = ds.copy()
	if vec[0] > mid:
		return False
	for i in range(1, n):
		if vec[i - 1] < mid:
			vec[i] = vec[i] - (mid - vec[i - 1])
			vec[i - 1] = mid
		if vec[i] > mid:
			return False
	if max(vec) > mid:
		return False
	return True

def play():
	n = int(input())
	vec = list(map(int, input().split()))
	i = 0
	j = max(vec)
	ans = 1000000000
	while i <= j:
		mid = (i + j) // 2
		if modeee(n, vec, mid):
			ans = min(ans, mid)
			j = mid - 1
		else:
			i = mid + 1
	print(ans)
tt = int(input())
for i in range(tt):
	play()


import sys
from typing import List

def is_valid_mid(n: int, ds: List[int], mid: int) -> bool:
	temp_vec_1 = ds.copy()
	if temp_vec_1[0] > mid:
		return False
	for i in range(1, n):
		if temp_vec_1[i - 1] < mid:
			temp_vec_1[i] = temp_vec_1[i] - (mid - temp_vec_1[i - 1])
			temp_vec_1[i - 1] = mid
		if temp_vec_1[i] > mid:
			return False
	if max(temp_vec_1) > mid:
		return False
	return True

def hook():
	num_ele = int(input())
	rve = list(map(int, input().split()))
	start_1 = 0
	end_1 = max(rve)
	ans_1 = 1000000000
	while start_1 <= end_1:
		midy = (start_1 + end_1) // 2
		if is_valid_mid(num_ele, rve, midy):
			ans_1 = min(ans_1, midy)
			end_1 = midy - 1
		else:
			start_1 = midy + 1
	print(ans_1)
num = int(input())
for i in range(num):
	hook()