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

Source: codechef | Difficulty: EASY
Tags: Complete search


Solutions:
for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += f[i]
		if ans == i:
			break
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	c = A[0]
	b = 0
	for j in range(1, len(A)):
		if c == 0:
			break
		c = c - 1 + A[j]
		b += 1
	if c > 0:
		b = b + c
	print(b)


import math
from collections import Counter

def solve():
	n = int(input())
	x = list(map(int, input().split()))
	a = 0
	b = 0
	for i in range(len(x)):
		a = a + x[i]
		if a == 0:
			print(b)
			return
		a -= 1
		b += 1
	print(a + b)
for _ in range(int(input())):
	solve()


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)


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


for _ in range(int(input())):
	n = int(input())
	N = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if count >= i:
			count += N[i]
	print(count)


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


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = l[0]
	c = l[0]
	for i in range(1, n):
		if b == 0:
			break
		b -= 1
		b += l[i]
		c += l[i]
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input().split()
	gas = int(a[0])
	unit = 0
	for i in range(1, len(a)):
		if gas == 0:
			break
		gas = gas - 1 + int(a[i])
		unit += 1
	print(unit + gas)


for tc in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	gas = 0
	unit = 0
	for i in range(n):
		gas = gas + f[i] - 1
		unit = unit + 1
		if gas < 0:
			break
	print(unit + gas)


for _ in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	G = a[0]
	D = 0
	for i in range(1, n):
		if G <= 0:
			break
		G = G - 1 + a[i]
		D += 1
	print(G + D)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	sum = 0
	for y in range(n):
		sum += a[y]
		if sum == y:
			break
	print(sum)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = d = b[0]
	for i in range(1, a):
		if c == 0:
			break
		c -= 1
		c += b[i]
		d += b[i]
	print(d)


for _ in range(int(input())):
	n = int(input())
	g = list(map(int, input().split()))
	i = 0
	d = 0
	gas = g[0]
	while gas != 0:
		gas -= 1
		if i < len(g) - 1:
			gas += g[i + 1]
			i += 1
		d += 1
	print(d)


for _ in range(int(input())):
	n = int(input())
	f = map(int, input().split())
	travel = 0
	for (i, k) in enumerate(f):
		if k > 0 and travel >= i:
			travel += k
	print(travel)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if 0 not in a:
		print(sum(a))
	elif a[0] == 0:
		print(0)
	else:
		x = 0
		y = a[0]
		for i in range(1, n):
			x += 1
			y += a[i]
			y -= 1
			if y == 0:
				break
		print(x + y)


for i in range(int(input())):
	x = int(input())
	fuel = list(map(int, input().split()))
	cur = 0
	distance = 0
	for j in range(x):
		if cur >= 0 or cur >= fuel[j]:
			cur = cur - 1 + fuel[j]
			distance += fuel[j]
		else:
			break
	print(distance)


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)


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


t = int(input())
for i in range(t):
	n = int(input())
	Fn = list(map(int, input().split()))
	f = 0
	for j in range(n):
		f = f + Fn[j]
		if j >= f:
			break
	print(f)


for i in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	l = f[0]
	u = 0
	for i in range(1, n):
		if l == 0:
			break
		l = l - 1 + f[i]
		u += 1
	print(l + u)


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)


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)


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)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	count = 0
	for i in range(n):
		k = k + l[i] - 1
		count += 1
		if k < 0:
			break
	print(k + count)


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)


for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	distance_travelled = []
	current_gas_litres = f[0]
	distance_travelled.append(current_gas_litres)
	for fi in f[1:]:
		if current_gas_litres == 0:
			break
		current_gas_litres -= 1
		current_gas_litres += fi
		distance_travelled.append(fi)
	print(sum(distance_travelled))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	d = 0
	for i in range(1, n):
		if g != 0:
			g = g - 1
			d = d + 1
			g = g + l[i]
	print(g + d)


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


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


t = int(input())
for tc in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = l[0]
	d = 0
	for j in range(1, n):
		if a != 0:
			a -= 1
			d += 1
			a += l[j]
	print(d + a)


t = int(input())
for t in range(t):
	n = int(input())
	f = [int(i) for i in input().split()]
	sum = f[0]
	i = 0
	dis = 0
	while sum != 0:
		sum = sum - 1
		if i < n - 1:
			sum += f[i + 1]
			i += 1
		dis += 1
	print(dis)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sm = 0
	for i in range(n):
		sm += a[i]
		if i >= sm:
			break
	print(sm)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()[:n]))
	c = 0
	d = 0
	s = sum(l)
	k = l[0]
	if l[0] == 0:
		print(0)
	elif l[0] >= n:
		print(s)
	else:
		for j in range(n):
			d = d + l[j]
			if d == 0:
				break
			c = c + l[j]
			d = d - 1
		print(c)


t = int(input())
while t > 0:
	N = int(input())
	li = list(map(int, input().split()))
	sum1 = li[0]
	count = 0
	if sum1 == 0:
		print(0)
	else:
		for i in range(1, N):
			sum1 = sum1 - 1 + li[i]
			if sum1 == 0:
				break
		if sum1 <= 0:
			print(i)
		else:
			print(sum1 + i)
	t -= 1


for i in range(int(input())):
	n = int(input())
	t = input().split()
	oil = int(t[0])
	dis = 0
	for i in range(1, n):
		if oil == 0:
			break
		oil = oil + int(t[i]) - 1
		dis = dis + 1
	if oil != 0:
		dis = dis + oil
	print(dis)


a = int(input(''))
for i in range(a):
	x = int(input(''))
	v = [int(x) for x in input('').split()]
	k = list(v)
	c = k[0]
	d = 0
	for j in range(1, len(k)):
		if c != 0:
			d = d + 1
			c = c + k[j] - 1
	print(c + d)


for _ in range(int(input())):
	N = int(input())
	F = list(map(int, input().split()))
	travel = 0
	for (i, f) in enumerate(F):
		if f > 0 and travel >= i:
			travel += f
	print(travel)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dist = 0
	fuel = arr[0]
	arr = arr[1:]
	while fuel > 0:
		temp = dist
		dist += fuel
		fuel = sum(arr[temp:dist])
	print(dist)


test = int(input())
for t in range(test):
	N = int(input())
	s = input().split(' ')
	for i in range(len(s)):
		s[i] = int(s[i])
	gas = s[0]
	dist = 0
	if gas == 0:
		print(0)
	else:
		for i in range(1, len(s)):
			dist += 1
			gas = gas - 1 + s[i]
			if gas == 0:
				break
		dist += gas
		print(dist)


T = int(input())
for tc in range(0, T):
	N = int(input())
	F = list(map(int, input().split(' ')))
	if F[0] < 1:
		print(0)
	else:
		i = 1
		dist = 0
		fuel = F[0]
		F[0] = 0
		while fuel != 0:
			fuel += F[i] - 1
			F[i] = 0
			i += 1
			dist += 1
			if i == N:
				i = 0
		print(dist)


T = int(input())
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	dist = 0
	fuel = 0
	for j in range(N):
		fuel += l[j]
		if fuel == 0:
			break
		dist += l[j]
		fuel -= 1
	print(dist)


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


t = int(input())
for v in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	p = l[0]
	d = 0
	while p > 0:
		d += 1
		p -= 1
		if d < n:
			p += l[d]
	print(d)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	fuel = a[0]
	dist = 0
	for j in range(1, len(a)):
		if fuel == 0:
			break
		fuel = fuel - 1 + a[j]
		dist += 1
	if fuel > 0:
		dist = dist + fuel
	print(dist)


T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split(' ')))
	ans = 0
	sum = 0
	for i in range(N):
		sum += arr[i] - 1
		ans += 1
		if sum < 0:
			break
	print(sum + ans)


t = int(input())
for tc in range(t):
	s = 0
	n = int(input())
	A = list(map(int, input().split(' ')))
	fu = A[0]
	for i in range(1, n):
		if fu >= 1:
			fu = fu + A[i] - 1
			s = s + 1
		else:
			break
	s += fu
	print(s)


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 t in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	k = f[0]
	l = 0
	for i in range(1, n):
		if k != 0:
			l += 1
			k = k + f[i] - 1
	print(l + k)


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)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	g = a[0]
	ans = 0
	if g > 0:
		for i in range(1, n):
			g -= 1
			g += a[i]
			ans += 1
			if g <= 0:
				break
	ans += g
	print(ans)


T = int(input())
for i in range(T):
	n = int(input())
	a = [int(j) for j in str(input()).split(' ')]
	i = 1
	f = a[0]
	d = 0
	while i < n and f > 0:
		f = f - 1
		f = f + a[i]
		d = d + 1
		i = i + 1
	while f > 0:
		d += 1
		f -= 1
	print(d)


for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	fuel = L[0]
	travelled = 0
	for i in range(1, len(L)):
		if fuel == 0:
			break
		fuel += L[i] - 1
		travelled += 1
	print(travelled + fuel)


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())
	a = [int(n) for n in input().split()]
	s = 0
	c = 0
	for j in range(n):
		s = s + a[j] - 1
		c = c + 1
		if s < 0:
			break
	print(c + s)


test_cases = int(input())
for test_case in range(test_cases):
	length = int(input())
	positions = [int(x) for x in input().split()]
	current_fuel = positions[0]
	total_distance = 0
	i = 0
	while current_fuel > 0:
		if i + 1 == len(positions):
			total_distance += current_fuel
			break
		current_fuel += positions[i + 1]
		total_distance += 1
		current_fuel -= 1
		i += 1
	print(total_distance)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(j) for j in input().split()]
	c = 0
	for k in range(n):
		if c >= k:
			a = l[k]
			c += a
	print(c)


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


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)


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 i in range(T):
	N = int(input())
	Ni = list(map(int, input().split()))
	gas = Ni[0]
	distance = 0
	for i in range(1, N):
		if gas == 0:
			break
		gas = gas - 1 + Ni[i]
		distance += 1
	print(gas + distance)


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 i in range(int(input())):
	N = int(input())
	cars = map(int, input().split())
	fuel = 0
	counter = 0
	for car in cars:
		fuel += car - 1
		counter += 1
		if fuel < 0:
			break
	print(fuel + counter)


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)


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())
	l = list(map(int, input().split()))
	if l[0] == 0:
		value = 0
	else:
		value = 0
		for i in range(n):
			value += l[i]
			if value < i + 1:
				break
	print(value)


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)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sum = 0
	c = 0
	for i in range(n):
		sum += a[i] - 1
		c = c + 1
		if sum < 0:
			break
	print(sum + c)


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


for i in range(int(input())):
	m = int(input())
	n = list(map(int, input().split()))
	p = l = n[0]
	for i in range(1, m):
		if p == 0:
			break
		p -= 1
		p += n[i]
		l += n[i]
	print(l)


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)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	temp = l[0]
	cnt = 0
	for i in range(1, n):
		if temp != 0:
			cnt = cnt + 1
			temp = temp + l[i] - 1
	print(cnt + temp)


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


for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	f = L[0]
	t = 0
	for i in range(1, len(L)):
		if f == 0:
			break
		f += L[i] - 1
		t += 1
	print(t + f)


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))[:n]
	sum = 0
	for j in range(n):
		sum += lst[j]
		if sum == j:
			break
	print(sum)


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	su = 0
	x = 0
	for i in range(n):
		if l[i] == 0 and su == 0:
			break
		su = su + l[i] - 1
		x = x + 1
	print(su + x)


t = int(input())
for i in range(t):
	n = int(input())
	f = list(map(int, input().split()))
	res = 0
	for i in range(len(f)):
		res = res + f[i]
		if i >= res:
			break
	print(res)