Chef wants to teach a lesson of sharing to the students.
There are $N$ students (numbered from $1$ to $N$ from left to right) who are asked to stand in a row. Initially Chef gave $A$$i$ candies to the $i$$th$ child. In one operation any child can give any number of candies to the child standing to his immediate left (i.e. $i$$th$ child can give any amount of candies to the $(i-1)$$th$ child. In particular 1st child cannot give his candies to anyone).  
He asked them to minimize the maximum value of candies a student can possess after performing any number of operations (possibly zero). 
Help the students finding such maximum value.

-----Input:-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- First line of each test case contains a single integer $N$ denoting the number of students.
- Second line contains $N$ space-separated integers $A$$1$,$A$$2$,$.....$ $A$$N$ denoting the initial amount of candies chef gave to them.

-----Output:-----
- For each test case, print a single line containing one integer ― maximum value after sharing.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 10^5$
- $0$ $\leq$ $A$$i$ $\leq$ $10^9$
- Sum of $N$ over all Test Cases does not exceed $10^5$

-----Sample Input-----
2 
5 
1 2 3 4 5 
5
5 4 3 2 1

-----Sample Output-----
3 
5  

-----Explanation-----
- 
For First Test Case:
The $5$$th$ student will give $2$ candies to $4$$th$ student and $4$$th$ will give $3$ candies to $3$$rd$ and $3$$rd$ will give $3$ candies to $2$$nd$ and $2$$nd$ will give $2$ candies to $1$$st$. So finally the number of candies that they will have are 
$[3,3,3,3,3]$ and the value of maximum candies is $3$.
- 
For Second Test Case:
Sharing to the left student will not change the maximum value as $1$$st$ cannot share to anyone. So the maximum value will remain $5$.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from math import ceil
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	sarr = sum(arr)
	mavg = sarr / n
	while n > 1:
		sarr -= arr.pop()
		n -= 1
		mavg = max(mavg, sarr / n)
	print(int(ceil(mavg)))


import math
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	left = 0
	for i in range(N):
		v = A[i] - ans - left
		if v < 0:
			left = -v
		else:
			ans = ans + math.ceil(v / (i + 1))
			left = math.ceil(v / (i + 1)) * (i + 1) - v
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = a[0]
	s = 0
	for i in range(n):
		s += a[i]
		if s % (i + 1) == 0:
			ans = max(ans, s // (i + 1))
		else:
			ans = max(ans, s // (i + 1) + 1)
	print(ans)


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