There are $N$ cars (numbered $1$ through $N$) on a circular track with length $N$. For each $i$ ($2 \le i \le N$), the $i$-th of them is at a distance $i-1$ clockwise from car $1$, i.e. car $1$ needs to travel a distance $i-1$ clockwise to reach car $i$. Also, for each valid $i$, the $i$-th car has $f_i$ litres of gasoline in it initially.
You are driving car $1$ in the clockwise direction. To move one unit of distance in this direction, you need to spend $1$ litre of gasoline. When you pass another car (even if you'd run out of gasoline exactly at that point), you steal all its gasoline. Once you do not have any gasoline left, you stop.
What is the total clockwise distance travelled by your car? 

-----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.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $f_1, f_2, \ldots, f_N$.

-----Output-----
For each test case, print a single line containing one integer ― the total clockwise distance travelled.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N \le 100$
- $0 \le f_i \le 100$ for each valid $i$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
3
5
3 0 0 0 0
5
1 1 1 1 1
5
5 4 3 2 1

-----Example Output-----
3
5
15

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
 n=int(input())
 f=list(map(int,input().split()))
 sum1=f[0]
 d=0
 i=1 
 while sum1!=0 and i<n:
  sum1=sum1-1+f[i]
  d+=1 
  i+=1 
 print(d+sum1)


t = int(input())

for _ in range(t):
 n = int(input())
 flag = 0
 
 f = [int(x) for x in input().split()]
 
 for i in range(1, n):
  f[i] += f[i-1]
 
 for i in range(0, n):
  if f[i] <= i:
   flag = 1
   break
 
 if(flag == 1):
  print(i)
 else:
  print(f[-1])

t = int(input())

for _ in range(t):
 n = int(input())
 flag = 0
 
 f = [int(x) for x in input().split()]
 
 for i in range(1, n):
  f[i] += f[i-1]
 
 for i in range(0, n):
  if f[i] <= i:
   flag = 1
   break
 
 if(flag == 1):
  print(i)
 else:
  print(f[-1])

t=int(input())

for i in range(1,t+1):
 n=int(input())
 lst=list(map(int,input().split()))
 l=0
 s=lst[0]
 for j in range(1,len(lst)):
  if s>=1:
   l+=1
   s-=1
   s+=lst[j]
  else:
   break

 ans=l+s
 print(ans)
  


t=0
t = int(input())

for i in range(0,t):
 n=0
 n = int(input())
 f =[]
 f = list(map(int,input().split()))
 
 total_fuel=f[0]
 total_dist=0
 i=1

 while(total_fuel>0 and total_dist<=n-1 and i<=n-1):
  total_fuel=total_fuel + f[i] - 1
  total_dist=i
  i = i+1

 if(total_fuel == 0):
  ans = total_dist
 else:
  ans = total_fuel + total_dist

 print(ans)

  


for _ in range(int(input())):
 n = int(input())
 arr = list(map(int,input().split()))
 dis = 0
 fuel = arr[0]
 for i in range(1,n):
  if fuel > 0:
   fuel -= 1
   dis += 1
   fuel += arr[i]
  else:
   break
 
 dis += fuel
 print(dis)


# cook your dish here
for _ in range(int(input())):
 n = int(input())
 l = list(map(int,input().split()))
 if l[0]==0:
  print(0)
 else:
  s = l[0]
  c = 0
  for i in range(1,len(l)):
   s-=1
   s+=l[i]
   c+=1
   if s==0:
    break
  print(s+c)

# cook your dish here
for i in range(int(input())):
 n = input()
 fuel = list(map(int, input().split()))
 sum = fuel[0]
 count = 0
 for j in range(1, len(fuel)):
  if sum==0:
   break
  else:
   sum = (sum-1)+fuel[j]
   count+=1
 print(count+sum)
 fuel.clear()

for i in range(int(input())):
 n=int(input())
 arr = list(map(int,input().split()))
 su=arr[0]
 count=0
 for j in range(1,n):
  if(su==0):
   break
  else:
   su=(su-1)+arr[j]
   count+=1
 print(su+count)
 arr.clear()
  


# cook your dish here
for u in range(int(input())):
 n = int(input())
 gas = list(map(int, input().split()))[:n]
 dist1 = 0
 dist = 0
 for i in gas:
  if i == 0 and dist == 0:
   break
  else:
   dist = dist+i
   dist -= 1
  dist1 += 1
 print(dist+dist1)

# cook your dish here
for t in range(int(input())):
  N = int(input())
  f = list(map(int, input().split()))
  gas = f[0]
  distance = 0
  for _ in range(1, N):
    if gas == 0:
      break
    gas = gas - 1 + f[_]
    distance += 1
  print(distance + gas) 



n=int(input())
li=[]
for i in range(n):
 N=int(input())
 l=list(map(int,input().split()))
 li.append(l)
def dist(lst):
 
 ptr=lst[0]
 dst=1
 
 for i in range(1,len(lst)):
  if ptr>=1:
   ptr-= 1
   ptr+=lst[i]
   dst+=1
  elif ptr==0:
   break
 dst+=ptr
 return dst
   
  
 
for k in li:
 print(dist(k)-1)
  
   

 
  
  
  
 
 
  




n=int(input())
li=[]
for i in range(n):
 N=int(input())
 l=list(map(int,input().split()))
 li.append(l)
def dist(lst):
 
 ptr=lst[0]
 dst=1
 
 for i in range(1,len(lst)):
  if ptr>=1:
   ptr-= 1
   ptr+=lst[i]
   dst+=1
  elif ptr==0:
   break
 dst+=ptr
 return dst
   
  
 
for k in li:
 print(dist(k)-1)
  
   

 
  
  
  
 
 
  



for _ in range(int(input())):
 n= int(input())
 arr =list(map(int,input().split()))
 curr_fuel =arr[0]
 count=0
 if arr[0]!=0:
  for i in range(1,n):
   curr_fuel -=1
   curr_fuel+=arr[i]
   count+=1
   if curr_fuel==0:
    break
  count+=curr_fuel
  
 print(count)

 
 # cook your dish here


# cook your dish here
for _ in range(int(input())):
 n=int(input())
 lst=list(map(int,input().split()))
 distance=0
 fuel=lst[0]
 for i in range(1,n):
  if fuel==0:
   break
  else:
   fuel+=lst[i]-1
   distance+=1
 print(distance+fuel)

for _ in range(int(input())):
 n = int(input())
 a = list(map(int, input().split()))
 res = 0
 gas = a[0]
 for i in range(1, len(a)):
  if gas <= 0:
   break
  else:
   gas -= 1
   res += 1
   gas += a[i]
 print(res + gas)

for t in range(int(input())):
 n = int(input())
 lst = list(map(int, input().split()))
 s = lst[0]
 dis = 0
 for i in range(1, len(lst)):
  if s <= 0:
   break
  s = s - 1 + lst[i]
  dis += 1
 print(s + dis)


# cook your dish here
for _ in range(int(input())):
 n=int(input())
 lst=list(map(int,input().split()))
 s=lst[0]
 
 dis=0
 for i in range(1,len(lst)):
  
  if s<=0:
    break
  s=s-1+lst[i]
  
  dis+=1
  
 print(s+dis)

for _ in range(int(input())):
 n = int(input())
 ar = list(map(int, input().split()))
 res = 0
 gas = ar[0]
 for i in range(1, len(ar)):
  if gas==0:
   break
  else:
   gas -= 1
   gas += ar[i]
   res += 1
 res += gas
 print(res)

t = int(input())
for i in range(t):
 flag = 1
 n = int(input())
 f = [ int(i) for i in input().split()]
 gas = 0
 for i in range(len(f)):
  gas += f[i]
  if gas==0:
   print(i)
   flag = 0
   break
  gas -= 1
 if flag:
  print(sum(f))

T=int(input())
for i in range(T):
 N=int(input())
 F=input().split()
 Gas=int(F[0])
 Distance=0
 while Gas!=0:
  Distance+=1
  try:
   Gas=Gas+int(F[Distance])-1
  except:
   Gas-=1
 print(Distance)

t = int(input())
for _ in range(t):
 n = int(input())
 arr = list(map(int, input().split()))
 d=0
 fuel=0
 for i in range(n):
  fuel+=arr[i]
  if fuel==0:
   break
  d+=1
  fuel-=1
 if fuel==0:
  print(d)
 else:
  print(d+fuel)


t=int(input())
for i in range(t):
 n=int(input())
 
 f=list(map(int, input().strip().split()))
 current_gasoline=0
 dist=0
 for cars in range(1, n+1):
  current_gasoline+=f[cars-1]
  if current_gasoline==0:
   break
  f[cars-1]=0
  
  dist+=1
  current_gasoline-=1 
  
   
  
 dist+=current_gasoline
 
 print(dist)