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$.

Difficulty: interview

Starter code:

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)
 #case 1




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))