Meera teaches a class of $n$ students, and every day in her classroom is an adventure. Today is drawing day!

The students are sitting around a round table, and they are numbered from $1$ to $n$ in the clockwise direction. This means that the students are numbered $1,2,3,\ldots,n-1,n$, and students $1$ and $n$ are sitting next to each other.

After letting the students draw for a certain period of time, Meera starts collecting their work to ensure she has time to review all the drawings before the end of the day. However, some of her students aren't finished drawing! Each student $\boldsymbol{i}$ needs $t_i$ extra minutes to complete their drawing. 

Meera collects the drawings sequentially in the clockwise direction, starting with student ID $\boldsymbol{x}$, and it takes her exactly $1$ minute to review each drawing. This means that student $\boldsymbol{x}$ gets $0$ extra minutes to complete their drawing, student $x+1$ gets $1$ extra minute, student $x+2$ gets $2$ extra minutes, and so on. Note that Meera will still spend $1$ minute for each student even if the drawing isn't ready. 

Given the values of $t_1,t_2,\ldots,t_n$, help Meera choose the best possible $\boldsymbol{x}$ to start collecting drawings from, such that the number of students able to complete their drawings is maximal. Then print $\boldsymbol{x}$ on a new line. If there are multiple such IDs, select the smallest one.

Input Format

The first line contains a single positive integer, $n$, denoting the number of students in the class. 

The second line contains $n$ space-separated integers describing the respective amounts of time that each student needs to finish their drawings (i.e., $t_1,t_2,\ldots,t_n$).

Constraints

$1\leq n\leq10^5$
$0\leq t_i\leq n$

Subtasks

$1\leq n\leq10^4$ for $30\%$ of the maximum score.

Output Format

Print an integer denoting the ID number, $\boldsymbol{x}$, where Meera should start collecting the drawings such that a maximal number of students can complete their drawings. If there are multiple such IDs, select the smallest one.
Sample Input 1
3
1 0 0
Sample Output 1
2
Explanation 1

Meera's class has $n=3$  students:

If $x=1$ , then only two students will finish.
The first student needs  $t_1=1$ extra minute to complete their drawing. If Meera starts collecting here, this student will never finish their drawing. Students  $2$ and $3$ 's drawings are already finished, so their drawings are ready when she collects them in the second and third minutes.

If $x=2$ , then all three students will finish.
The second student needs $t_2=0$  extra minutes, so the drawing is ready for Meera to collect. The next (third) student's drawing is also ready one minute later, as $t_3=0$ . Meera then proceeds to the next (first) student, who needed $t_1=1$ extra minute. Because she already spent two minutes collecting the work of the other two students, the first student's drawing has already been completed for $2-1=1$ minute.

If $x=3$ , then all three students will finish.
The third student needs $t_3=0$ extra minutes, so the drawing is ready for Meera to collect. The next (first) student's drawing is also ready one minute later, as  $t_1=1$ and  $1$ minute passed while Meera collected the third student's drawing. She then proceeds to the next (second) student, whose drawing was already completed (as $t_2=0$ )

Starting with student IDs $x=2$   or  $x=3$ will result in a maximum number of completed drawings (i.e.,$3$ ). Because there are two equally valid answers, we choose the smaller ID, $2$, and print it as our answer.

Sample Input 2
3
0 1 2
Sample Output 2
1

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import sys
n = int(sys.stdin.readline())
t = [int(x) for x in sys.stdin.readline().split()]
current_available = 0
become_unavailable = [0] * (3 * n)
best_index = 1
best_result = 0
for i in range(2 * n):
	el = t[i % n]
	become_unavailable[i + (n - el)] += 1
	if current_available > best_result:
		best_result = current_available
		best_index = i % n + 1
	if current_available == best_result:
		best_index = min(i % n + 1, best_index)
	current_available += 1
	current_available -= become_unavailable[i]
print(best_index)


n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	a[i] = i - a[i]
p = len(list(filter(lambda x: x >= 0, a)))
d = [0 for _ in range(3 * n + 1)]
for x in a:
	d[x] += 1
(bestp, besti) = (p, 1)
for i in range(1, n):
	d[a[i - 1]] -= 1
	d[a[i - 1] + n] += 1
	if a[i - 1] + n >= 0 and a[i - 1] - i + 1 < 0:
		p += 1
	p -= d[i - 1]
	if p > bestp:
		(bestp, besti) = (p, i + 1)
print(besti)


n = int(input())
t = list(map(int, input().split()))
diag = [0] * n
bad = 0
for (i, ti) in enumerate(t):
	if ti:
		diag[(n + i - (ti - 1)) % n] += 1
	if ti > i:
		bad += 1
minbad = bad
mini = 0
for i in range(1, n):
	bad += diag[i]
	bad -= int(t[i - 1] != 0)
	if bad < minbad:
		mini = i
		minbad = bad
print(mini + 1)


n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
	b.append(0)
for i in range(n):
	if a[i] > 0:
		if a[i] <= i:
			b[i - a[i] + 1] -= 1
		else:
			b[(n - a[i] + i + 1) % n] -= 1
		b[(i + 1) % n] += 1
ans_pos = 0
ans_sum = 0
s = 0
for i in range(1, n):
	s += b[i]
	if s > ans_sum:
		ans_sum = s
		ans_pos = i
print(ans_pos + 1)


from operator import itemgetter
n = int(input())
xs = [int(x) for x in input().split()]
limes = [0] * n
res = 0
opened_brackets = 0
for i in range(len(xs)):
	if xs[i] == 0:
		res += 1
	elif xs[i] != n:
		start = (i + 1) % n
		end = (i - xs[i] + 1) % n
		limes[start] += 1
		limes[end] -= 1
		if end < start:
			opened_brackets += 1
res += opened_brackets
best_i = 0
best_res = None
for i in range(n):
	res += limes[i]
	if best_res is None or res > best_res:
		best_res = res
		best_i = i
print(best_i + 1)


n = int(input())
t = list(map(int, input().strip().split()))
t_in = []
t_out = []
for i in range(n):
	k = i - t[i] + 1
	if k < 0:
		k += n
	t_in.append((i + 1) % n)
	t_out.append(k)
t_in.sort()
i1 = 0
t_out.sort()
i2 = 0
cur_sum = 0
max_sum = 0
max_i = 0
for i in range(n):
	while i1 < n and t_in[i1] == i:
		cur_sum += 1
		i1 += 1
	while i2 < n and t_out[i2] == i:
		cur_sum -= 1
		i2 += 1
	if cur_sum > max_sum:
		max_i = i
		max_sum = cur_sum
print(max_i + 1)


n = int(input())
a = [int(i) for i in input().strip().split(' ')]
s = 0
p = 0
li = {}
for x in range(n):
	li[0 - x] = 0
for x in range(n):
	if a[x] - x < 1:
		li[a[x] - x] += 1
		s += 1
if s == n:
	print(p + 1)
else:
	k = s
	for x in range(1, n):
		k -= li[1 - x]
		li[1 - x] = 0
		a[x - 1] -= n - 1
		if a[x - 1] < 1:
			if a[x - 1] - x >= 1 - n:
				li[a[x - 1] - x] += 1
			k += 1
		if k > s:
			s = k
			p = x
		if s == n:
			break
	print(p + 1)


n = int(input())
t = list(map(int, input().split()))
starts = []
ends = []
maxCount = 0
ready = 0
for i in range(n):
	if t[i] == 0:
		ready += 1
	elif t[i] < n:
		start = (i + 1) % n
		end = (i - t[i] + n) % n
		if start <= end:
			starts.append(start)
			ends.append(end)
		else:
			starts.append(0)
			ends.append(end)
			starts.append(start)
			ends.append(n)
starts.sort()
ends.sort()
startIndex = 0
endIndex = 0
currCount = 0
bestTime = 0
while startIndex < len(starts):
	nextTime = min(starts[startIndex], ends[endIndex])
	while startIndex < len(starts) and starts[startIndex] == nextTime:
		startIndex += 1
		currCount += 1
	if currCount > maxCount:
		bestTime = nextTime
		maxCount = currCount
	while endIndex < len(ends) and ends[endIndex] == nextTime:
		endIndex += 1
		currCount -= 1
print(bestTime + 1)


n = int(input().strip())
arr = [int(a) for a in input().split()]
dic = {}
for i in range(n + 1):
	dic[i] = []
	dic[-i] = []
count_above = 0
count_below = 0
for i in range(n):
	dist = i - arr[i]
	if dist >= 0:
		count_below += 1
	else:
		count_above += 1
	dic[dist].append(i)
record_forward = [-1 for i in range(n)]
record_forward[0] = count_below
for i in range(1, n):
	temp = record_forward[i - 1]
	if len(dic[i - 1]) > 0:
		for j in dic[i - 1]:
			temp -= 1
	record_forward[i] = temp
pointstoadd = [0 for i in range(n)]
pointstoadd.append(count_below)
for (i, k) in zip(range(n - 1, -1, -1), range(1, n)):
	temp = pointstoadd[i + 1]
	if len(dic[-k]) > 0:
		for j in dic[-k]:
			temp += 1
	pointstoadd[i] = temp - 1
record = [record_forward[j] + pointstoadd[j] for j in range(n)]
print(record.index(max(record)) + 1)


from collections import defaultdict

def main():
	n = int(input())
	a = list(map(int, input().split()))
	intervals = defaultdict(int)
	count = 0
	for i in range(n):
		size = n - a[i]
		start = (i + 1) % n
		end = (i + 1 + n - a[i]) % n
		if end >= start:
			count += 1
		intervals[start] += 1
		intervals[end] -= 1
	start_pos = 0
	score = count + intervals[0]
	for t in range(n):
		count += intervals[t]
		if count > score:
			start_pos = t
			score = count
	print(start_pos + 1)
main()


kids = int(input())
times = list(map(int, input().split()))
hurrying = [0] * kids
x = [0] * kids
for i in range(kids):
	hurrying[(i + 1 - times[i]) % kids] += 1
	x[0] += max(0, times[i] - i)
for i in range(1, kids):
	x[i] = x[i - 1] + hurrying[i] - 1
print(min(map(lambda i: (x[i], i), range(kids)))[1] + 1)


n = int(input())
t = [int(t_i) for t_i in input().split(' ')]
starts = [0] * n
ends = [0] * n
ranges = set()
for i in range(0, n):
	k = t[i]
	start = (i + 1) % n
	end = (n - k + i + 1) % n
	if start >= end:
		starts[0] += 1
		starts[start] += 1
		ends[end] += 1
		ends[n - 1] += 1
	else:
		starts[start] += 1
		ends[end] += 1
max_idx = -1
max_count = 0
count = 0
for j in range(0, n):
	count += starts[j] - ends[j]
	if count > max_count:
		max_idx = j
		max_count = count
print(max_idx + 1)


from collections import Counter
n = int(input())
nums = [int(p) for p in input().strip().split(' ')]
stat = [i - nums[i] for i in range(n)]
cnt = Counter(stat)
init = result = sum([v for (k, v) in cnt.items() if k >= 0])
index = 0
max_value = init
for i in range(1, n):
	org_stat = -nums[i - 1]
	new_stat = n - 1 - nums[i - 1]
	rel_zero = i - 1
	tail = 0
	if org_stat >= 0 and new_stat >= 0 or (org_stat < 0 and new_stat < 0):
		tail = 0
	elif org_stat >= 0 and new_stat < 0:
		tail = -1
	else:
		tail = 1
	if stat[i - 1] != rel_zero:
		result = result - cnt[rel_zero] + tail
	else:
		result = result - (cnt[rel_zero] - 1) + tail
	cnt[org_stat + i - 1] -= 1
	cnt[new_stat + i] += 1
	if result > max_value:
		max_value = result
		index = i
if init == max_value:
	print(1)
else:
	print(index + 1)


from operator import itemgetter
n = int(input())
stuff = [0] * (n * 2 + 1)
x_time = [int(t) for t in input().split(' ')]
for (idx, xt) in enumerate(x_time):
	if xt != 0:
		stuff[n + idx - xt + 1] += 1
		stuff[n + idx + 1] -= 1
for i in range(1, n * 2 + 1):
	stuff[i] += stuff[i - 1]
new_stuff = stuff[:n]
for i in range(n):
	new_stuff[i] += stuff[i + n]
print(min(enumerate(new_stuff), key=lambda t: t[::-1])[0] + 1)


import heapq
num_students = int(input())
times = list(map(int, input().split()))
heap = []
num_slow = 0
for (i, time) in enumerate(times):
	if i < time:
		num_slow += 1
	else:
		heap.append((i - time, i))
heapq.heapify(heap)
max_students = num_students - num_slow
pos = 0
for start in range(1, num_students + 1):
	if times[start - 1] < num_students:
		num_slow -= 1
		heapq.heappush(heap, (num_students - 1 - times[start - 1] + start, start - 1))
	while True:
		if not heap or heap[0][0] >= start:
			break
		heapq.heappop(heap)
		num_slow += 1
	if num_students - num_slow > max_students:
		max_students = num_students - num_slow
		pos = start
print(pos + 1)


n = int(input())
ts = list(map(int, input().split()))
start = []
end = []
for i in range(n):
	t = ts[i]
	if t > 0 and t < n:
		if t > i:
			start.append(i + 1)
			end.append(n - t + i)
		else:
			start.append(0)
			end.append(i - t)
			if i + 1 < n:
				start.append(i + 1)
				end.append(n - 1)
start.sort()
end.sort()
maxOverlap = 0
maxStart = 0
cnt = 0
(i, j) = (0, 0)
m = len(start)
while i < m and j < m:
	if start[i] <= end[j]:
		cnt += 1
		if cnt > maxOverlap:
			maxOverlap = cnt
			maxStart = start[i]
		i += 1
	else:
		cnt -= 1
		j += 1
print(maxStart + 1)


n = int(input().strip())
t = input().strip().split(' ')
for i in range(0, len(t)):
	t[i] = int(t[i])
integrand = [0 for i in range(0, len(t))]
for i in range(0, len(t)):
	if t[i] == n:
		continue
	integrand[(i + 1) % n] += 1
	integrand[(i - t[i] + 1) % n] -= 1
successes = 0
for i in range(0, len(t)):
	if t[i] <= i:
		successes += 1
bestSuccesses = 0
bestSuccessesVal = -1
for i in range(0, len(t)):
	successes += integrand[i]
	if successes > bestSuccessesVal:
		bestSuccesses = i
		bestSuccessesVal = successes
print(bestSuccesses + 1)


n = int(input())
ts = list(map(int, input().split()))
cc = [0 for i in range(n)]
cc1 = 0
for (i, t) in enumerate(ts):
	if t > 0 and t < n:
		(l, r) = (i + 1, i - t + 1)
		l %= n
		r %= n
		cc[l] += 1
		cc[r] -= 1
(x, w) = (-1, -1)
for (i, c) in enumerate(cc):
	cc1 += c
	if cc1 > w:
		w = cc1
		x = i
print(x + 1)


import sys
n = int(sys.stdin.readline())
t = [int(i) for i in sys.stdin.readline().split()]
begin = [0 for i in range(n)]
end = [0 for i in range(n)]
current = best = ans = 0
for i in range(n):
	if t[i] < n:
		b = (i + 1 + n) % n
		e = (i - t[i] + n) % n
		begin[b] += 1
		end[e] += 1
		if b > e:
			current += 1
		print(b, e, current, file=sys.stderr)
print('*' * 80, file=sys.stderr)
print('Initial: {0}'.format(current), file=sys.stderr)
for i in range(n):
	current += begin[i]
	print('At {0}: {1}'.format(i, current), file=sys.stderr)
	if current > best:
		best = current
		ans = i
	current -= end[i]
print(ans + 1)


def fix_interval(x, y, n):
	if x >= n and y >= n:
		yield (x % n, y % n)
	elif y >= n:
		yield (x, n - 1)
		yield (0, y % n)
	else:
		yield (x, y)
n = int(input())
asked = list(map(int, input().split())) * 2
intervals = list()
for i in range(n, 2 * n):
	start = i - asked[i]
	if start >= i - n + 1:
		for (x, y) in fix_interval(i - n + 1, start, n):
			intervals.append((x, +1))
			intervals.append((y, -1))
intervals.sort(key=lambda x: (x[0], -x[1]))
result = 0
result_i = 0
current = 0
for (x, y) in intervals:
	current += y
	if current > result:
		result_i = x
		result = current
print(result_i + 1)


n = int(input().strip())
time_list = list(map(int, input().strip().split()))
sums = 0
start_end = []
end = []
for i in range(n):
	start = (i + n - time_list[i]) % n
	if start < i:
		start_end.append(('s', 1))
		start_end.append(('e', start + 2))
		if i < n - 1:
			start_end.append(('s', i + 2))
	elif start > i:
		start_end.append(('s', i + 2))
		if start < n - 1:
			start_end.append(('e', start + 2))
start_end.sort(key=lambda x: x[1])
num_drawings = {}
curr_drawings = 0
for (k, v) in start_end:
	if k == 's':
		curr_drawings += 1
	if k == 'e':
		curr_drawings -= 1
	num_drawings[v] = curr_drawings
maxed_id = 1
curr_max = -1
for v in num_drawings:
	if num_drawings[v] == curr_max and maxed_id > v:
		maxed_id = v
	elif num_drawings[v] > curr_max:
		curr_max = num_drawings[v]
		maxed_id = v
print(maxed_id)


n = input()
n = int(n)
ti = [int(x_temp) for x_temp in input().strip().split(' ')]
ranges = []
for i in range(n):
	mi = i + 2
	if mi > n:
		mi = 1
	ma = i + 1 - ti[i]
	if ma <= 0:
		ma = ma + n
		if ma == i + 1:
			continue
	if mi > ma:
		ranges.append((mi, n))
		ranges.append((1, ma))
	else:
		ranges.append((mi, ma))
max_studs = studs = 0
(start, end) = (0, 1)
events = sorted((event for r in ranges for event in zip(r, (start, end))))
for (start_pt, start_or_end) in events:
	studs += start_or_end == start
	studs -= start_or_end == end
	if studs > max_studs:
		answer = start_pt
		max_studs = studs
print(answer)


n = int(input())
lst = [int(i) for i in input().split()]
points = []
for i in range(n):
	(lp, rp) = (0, i - lst[i])
	if lp <= rp:
		points.append((lp, 0))
		points.append((rp, 1))
	(lp, rp) = (i + 1, n - lst[i] + i)
	if lp <= rp:
		points.append((lp, 0))
		points.append((rp, 1))
points = sorted(points, key=lambda x: x[0] + 0.1 * x[1])
(m, day, c) = (0, -1, 0)
for (t, ae) in points:
	if ae == 0:
		c += 1
	if c > m:
		(m, day) = (c, t)
	if ae == 1:
		c -= 1
print(day + 1)


n = int(input())
data = [int(x) for x in input().split()]
neg = [0 for i in range(n)]
pos = [0 for i in range(n)]
score = n
for i in range(n):
	if data[i] != 0:
		pos[(i + 1) % n] += 1
		neg[(i - data[i] + 1) % n] += 1
	if i + 1 <= data[i]:
		score -= 1
ans = 0
m_score = score
for i in range(1, n):
	score += pos[i]
	score -= neg[i]
	if score > m_score:
		m_score = score
		ans = i
print(ans + 1)


def solve(a, b, arr):
	arr[a] = arr[a] + 1
	if b + 1 < len(l):
		arr[b + 1] -= 1
n = int(input())
l = [int(i) for i in input().split(' ')]
d = {}
maxOcc = -1
maxPos = -1
arr = [0] * n
for i in range(len(l)):
	if l[i] >= n:
		continue
	index = (i - l[i] + n) % n
	s = (i + 1) % n
	if index < s:
		solve(s, len(l), arr)
		solve(0, index, arr)
	else:
		solve(s, index, arr)
x = 0
for i in range(len(arr)):
	x = x + arr[i]
	if x > maxOcc:
		maxOcc = x
		maxPos = i
print(maxPos + 1)


def findMaxOverlapPoint(arrl, exit):
	n = len(arrl)
	arrl.sort()
	exit.sort()
	guests_in = 1
	max_guests = 1
	time = arrl[0]
	i = 1
	j = 0
	while i < n and j < n:
		if arrl[i] <= exit[j]:
			guests_in += 1
			if guests_in > max_guests:
				max_guests = guests_in
				time = arrl[i]
			i += 1
		else:
			guests_in -= 1
			j += 1
	return time
n = int(input())
intrvl_s = []
intrvl_e = []
l = list(map(int, input().split()))
for i in range(n):
	if l[i] >= n:
		continue
	if l[i] == 0:
		intrvl_s.append(0)
		intrvl_e.append(n - 1)
		continue
	start = i + 1
	end = i - l[i]
	if end < 0:
		intrvl_s.append(start)
		intrvl_e.append(end % n)
	else:
		intrvl_s.append(start)
		intrvl_e.append(n - 1)
		intrvl_s.append(0)
		intrvl_e.append(end)
print(findMaxOverlapPoint(intrvl_s, intrvl_e) + 1)


import sys
T = int(input())
L = [0]
for n in input().split():
	L.append(int(n))
starting = []
ending = []
i = 1
i1 = 0
i2 = 0
for n in L[1:]:
	if n == 0:
		starting.append(1)
		ending.append(T)
	elif n == T:
		pass
	elif T - n <= T - i:
		if i != T:
			starting.append(i + 1)
			ending.append(i + T - n)
	else:
		if i != T:
			starting.append(i + 1)
			ending.append(T)
		if i != 1:
			starting.append(1)
			ending.append(i - n)
	i += 1
starting.sort()
ending.sort()
slen = len(starting)
elen = len(ending)
i = 0
j = 0
curmax = 0
tmax = 0
nmax = 0
while i < slen and j < elen:
	if ending[j] < starting[i]:
		curmax -= 1
		j += 1
	else:
		curmax += 1
		if curmax > tmax:
			tmax = curmax
			nmax = starting[i]
		i += 1
while i < slen:
	curmax += 1
	if curmax > tmax:
		tmax = curmax
		nmax = starting[i]
	i += 1
sys.stdout.write(str(nmax))


def main():
	n = int(input())
	t = list(map(int, input().split()))
	if min(t) >= n:
		print(1)
		exit()
	c = [0] * (n + 1)
	for i in range(n):
		if t[i] == n:
			continue
		temp = (i - t[i]) % n
		c[(i + 1) % n] += 1
		c[temp] -= 1
	for i in range(1, n):
		c[i] += c[i - 1]
	(res, mx) = (0, c[0])
	for (i, x) in enumerate(c):
		if x > mx:
			res = i
			mx = x
	if mx == 0 and res == 0:
		print(1)
	else:
		print((res + 1 + n) % n + 1)
main()


n = int(input())
students = []
s0 = 0
inp = input().split()
for i in range(n):
	t = int(inp[i])
	if t == 0:
		s0 += 1
	elif t < n:
		students.append([(i + 1) % n, 1])
		students.append([(i - t + n) % n, -1])
		if (i - t + n) % n < (i + 1) % n:
			s0 += 1
students.sort(key=lambda x: (x[0], -x[1]))
s1 = s0
m = s1
m_i = 0
for s in students:
	s1 = s1 + s[1]
	if s1 > m:
		m = s1
		m_i = s[0]
print(m_i + 1)


n = int(input())
time = list(map(int, input().split(' ')))
score = [0 for i in range(n + 1)]
b = [0 for i in range(n + 1)]
if n == 1:
	if time[0] == 0:
		b[0] = 1
	else:
		b[0] = 0
else:
	for i in range(n):
		x = time[i]
		if x == 0:
			score[0] += 1
			score[n] -= 1
			continue
		if x > i:
			beg = i + 1
			last = n - (x - i) + 1
			score[beg] += 1
			score[last] -= 1
		else:
			beg = 0
			last = i - x + 1
			score[beg] += 1
			score[last] -= 1
			if i < n - 1:
				beg = i + 1
				last = n
				score[beg] += 1
				score[last] -= 1
	for i in range(n):
		if i == 0:
			b[i] = score[i]
		else:
			b[i] = b[i - 1] + score[i]
maximum = 'true'
indx = 0
for i in range(len(b)):
	if maximum == 'true':
		maximum = b[i]
		indx = i
	elif b[i] > maximum:
		maximum = b[i]
		indx = i
print(indx + 1)


from bisect import bisect_left, insort

def solve(Ts):
	n = len(Ts)
	times = sorted((i - t for (i, t) in enumerate(Ts)))
	Nbs = []
	nb = 0
	for i in range(n):
		while nb < n and times[nb] < i:
			nb += 1
		Nbs.append(nb)
		del times[bisect_left(times, i - Ts[i])]
		insort(times, i - Ts[i] + n)
		if nb > 0:
			nb -= 1
	return Nbs
n = int(input())
Ts = list(map(int, input().split()))
Nbs = solve(Ts)
print(Nbs.index(min(Nbs)) + 1)


def find(l):
	d_p = {key: 0 for key in range(len(l))}
	d_n = {key: 0 for key in range(len(l))}
	for (i, j) in enumerate(l):
		if j == 0:
			continue
		else:
			d_p[(i + 1) % len(l)] += 1
			d_n[(i - (j - 1)) % len(l)] += 1
	max_s = d_p[0] - d_n[0]
	cont_sum = 0
	index = 0
	for i in range(len(l)):
		cont_sum += d_p[i] - d_n[i]
		if cont_sum > max_s:
			max_s = cont_sum
			index = i
	return index + 1
n = int(input().strip())
l = [int(i) for i in input().strip().split()]
print(find(l))


n = int(input())
t = [int(x) for x in input().split(' ')]
startPoints = {}
endPoints = {}
students = {}
setCount = 0

def addTo(val, d, amount):
	if val not in d:
		d[val] = amount
	else:
		d[val] += amount

def addToStart(start, d, end):
	if start not in d:
		d[start] = [end]
	else:
		d[start] += [end]
for i in range(len(t)):
	val = t[i]
	if not (val == 0 or val > len(t) - 1):
		end = i - val + 1
		if end < 0:
			end = len(t) + end
		start = i + 1
		if start > len(t) - 1:
			start = start - len(t)
		addToStart(start, startPoints, end)
		addTo(end, endPoints, 1)
	if val <= i:
		if val != 0:
			addTo(end, students, 1)
		setCount += 1
x = 0
best = setCount
for i in range(1, len(t)):
	additions = startPoints[i] if i in startPoints else []
	reductions = students[i] if i in students else 0
	setCount += len(additions)
	setCount -= reductions
	if setCount > best:
		x = i
		best = setCount
	if reductions > 0:
		students[i] = 0
	if additions:
		for end in additions:
			addTo(end, students, 1)
print(x + 1)


numStudents = int(input())
students = [int(student) for student in input().split(' ')]
diff = [0] * numStudents
for index in range(numStudents):
	if 0 < students[index] and students[index] < numStudents:
		diff[(index + 1) % numStudents] += 1
		diff[(index - students[index] + 1) % numStudents] -= 1
curSum = 0
maxSum = diff[0]
bestIndex = 0
for index in range(numStudents):
	curSum += diff[index]
	if curSum > maxSum:
		maxSum = curSum
		bestIndex = index
print(bestIndex + 1)


n = int(input())
times = list(map(int, input().split()))
deltas = [0] * n
for (i, t) in enumerate(times, start=0):
	delta = 1 if t % n else 0
	deltas[(n + i - t + 1) % n] -= delta
	deltas[(i + 1) % n] += delta
start = sum([i >= t for (i, t) in enumerate(times)])
done = [start] * n
for i in range(1, n):
	done[i] = done[i - 1] + deltas[i]
print(max(enumerate(done, start=1), key=lambda x: x[1])[0])


import sys
N = int(sys.stdin.readline())
T = list(map(int, sys.stdin.readline().split()))
X = [x - T[x] for x in range(0, N)]
S = sorted([(x - T[x], x) for x in range(0, N)], key=lambda tup: tup[0])
A = sum((X[i] >= 0 for i in range(0, N - 1)))
bestA = A
Ans = 1
rindex = 0
lindex = 0
while rindex < N and S[rindex][0] < 0:
	rindex += 1
while lindex < N and S[lindex][0] < -N:
	lindex += 1
for i in range(0, N - 1):
	if X[i] >= i:
		A -= 1
	if X[i] >= i - N + 1:
		A += 1
	while rindex < N and S[rindex][0] <= i:
		if S[rindex][1] > i:
			A -= 1
		rindex += 1
	while lindex < N and S[lindex][0] <= i - N:
		if S[lindex][1] < i:
			A -= 1
		lindex += 1
	if A > bestA:
		bestA = A
		Ans = i + 2
print(Ans)


n = int(input().strip())
tlist = [int(c) for c in input().strip().split(' ')]
points = {}

def inc(i):
	points.setdefault(i, 0)
	points[i] += 1

def dec(i):
	points.setdefault(i, 0)
	points[i] -= 1
for i in range(n):
	ti = tlist[i]
	if ti in (0, n):
		continue
	dec((i - ti + 1) % n)
	inc((i + 1) % n)
rsum = 0
rsummax = -10 * 9
rindex = -1
for i in range(n):
	rsum += points.get(i, 0)
	if rsum > rsummax:
		rsummax = rsum
		rindex = i
print(rindex + 1)


n = int(input().strip())
a = list(map(int, input().strip().split()))
b = [0 for i in range(n)]
for i in range(n):
	v = a[i]
	if 0 == v or v >= n - 1:
		continue
	i1 = i - v + 1
	i2 = i + 1
	if i1 < 0:
		i1 += n
	if i2 >= n:
		i2 -= n
	b[i1] -= 1
	b[i2] += 1
(result, mv, tmp) = (0, 0, 0)
for i in range(n):
	tmp += b[i]
	if 0 == i or tmp > mv:
		result = i
		mv = tmp
print(result + 1)


N = int(input())
delay = list(map(int, input().split(' ')))
limit = [[] for i in range(N)]
unfinished = [0 for i in range(N)]
curunfinished = [False for i in range(N)]
sumcurunfinished = 0
for i in range(N):
	if delay[i] >= 1:
		limit[(i - delay[i]) % N].append(i)
i = 0
while i < N or sumcurunfinished != 0:
	unfinished[i % N] += sumcurunfinished
	if curunfinished[i % N]:
		curunfinished[i % N] = False
		sumcurunfinished -= 1
	for j in limit[i % N]:
		curunfinished[j] = True
		sumcurunfinished += 1
	limit[i % N] = []
	i += 1
mini = unfinished[0]
miniindex = 0
for i in range(1, N):
	if mini > unfinished[i]:
		mini = unfinished[i]
		miniindex = i
print(miniindex + 1)


import sys

def incRange(l, first, last):
	for i in range(first, last + 1):
		l[i] = l[i] + 1

def setIncHigh(l, idx, inc):
	if idx >= len(l):
		return
	l[idx][2] = l[idx][2] + inc

def setIncLow(l, idx, inc):
	if idx >= len(l):
		return
	l[idx][0] = l[idx][0] + inc
lines = sys.stdin.readlines()
n = int(lines[0])
tab = [int(x) for x in lines[1].split()]
tabX = []
for i in range(n):
	tabX.append([0, 0, 0])
for i in range(n):
	x = tab[i]
	if i + 1 > x:
		setIncHigh(tabX, i, 1)
		setIncLow(tabX, i - x + 1, 1)
	else:
		setIncLow(tabX, n - x + i + 1, 1)
		setIncLow(tabX, i + 1, -1)
for i in range(1, n):
	tabX[i][1] = tabX[i][1] + tabX[i - 1][2]
	tabX[i][2] = tabX[i][2] + tabX[i - 1][2]
for i in reversed(range(0, n - 1)):
	tabX[i][1] = tabX[i][1] + tabX[i + 1][0]
	tabX[i][0] = tabX[i][0] + tabX[i + 1][0]
maxIdx = 0
maxValue = 0
for i in range(n):
	if tabX[i][1] > maxValue:
		maxValue = tabX[i][1]
		maxIdx = i
print(maxIdx + 1)


numStudents = int(input())
timeList = [int(x) for x in input().split(' ')]
finishList = [0 for i in range(numStudents)]
for i in range(numStudents):
	if timeList[i] == 0:
		continue
	elif timeList[i] >= numStudents:
		continue
	else:
		finishList[(i + 1) % numStudents] += 1
		finishList[(i + 1 - timeList[i]) % numStudents] -= 1
largestIndex = 0
largestFinisher = -1000000
currentFinisher = 0
for i in range(2 * numStudents):
	currentFinisher = currentFinisher + finishList[i % numStudents]
	if currentFinisher > largestFinisher:
		largestFinisher = currentFinisher
		largestIndex = i % numStudents
print(largestIndex + 1)


import heapq

class Child:

	def __init__(self, time, index, size):
		self.time = time
		self.index = index
		self.size = size

	def is_past_threshold(self, starting_index):
		return (self.index - starting_index) % self.size < self.time

	def threshold_index(self):
		return (self.index - self.time + 1) % self.size

	def __lt__(self, other):
		return self.index < other.index

	def __gt__(self, other):
		return self.index > other.index

	def __eq__(self, other):
		return self.index == other.index

def count_wins(arr):
	at_risk_heap = []
	totals = {0: 0}
	for (i, child_time) in enumerate(arr):
		if child_time != 0:
			child = Child(child_time, i, len(arr))
			if not child.is_past_threshold(0):
				heapq.heappush(at_risk_heap, [child.threshold_index(), child])
				totals[0] += 1
	for starting_index in range(1, len(arr)):
		totals[starting_index] = totals[starting_index - 1]
		while at_risk_heap and at_risk_heap[0][0] == starting_index:
			heapq.heappop(at_risk_heap)
			totals[starting_index] -= 1
		popped_index = starting_index - 1
		child_time = arr[popped_index]
		if child_time != 0 and child_time < len(arr):
			child = Child(child_time, popped_index, len(arr))
			threshold_index = child.threshold_index()
			if threshold_index > starting_index and threshold_index < len(arr):
				heapq.heappush(at_risk_heap, [threshold_index, child])
			totals[starting_index] += 1
	return get_best(totals)

def get_best(counts):
	max_i = 0
	max_x = 0
	for (i, value) in counts.items():
		if value > max_x:
			max_i = i
			max_x = value
	return max_i
n = int(input().strip())
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
print(count_wins(arr) + 1)


n = int(input().strip())
arr = list(map(int, input().strip().split(' ')))

def find_max_collected(arr):
	l = len(arr)
	d = [0] * l
	for i in range(l):
		if arr[i] >= l or arr[i] == 0:
			pass
		else:
			indl = (i - arr[i] + 1) % l
			indr = (i + 1) % l
			d[indl] = d[indl] - 1
			d[indr] = d[indr] + 1
	max_val = -l
	min_ind = 0
	run_sum = 0
	for i in range(l):
		run_sum = run_sum + d[i]
		if max_val < run_sum:
			min_ind = i
			max_val = run_sum
	return min_ind
print(find_max_collected(arr) + 1)


from itertools import accumulate
n = int(input())
dp = [0] * n
for (i, t) in enumerate((int(x) for x in input().split())):
	if t == 0 or t == n:
		continue
	dp[(i + 1) % n] += 1
	dp[(i - t + 1) % n] -= 1
print(max(enumerate(accumulate(dp)), key=lambda x: x[1])[0] + 1)


n = int(input())
A = [0] * (n + 1)
for (i, x) in enumerate(map(int, input().split())):
	r1 = max(-1, i - x) + 1
	r2 = min(max(i, i - x + n) + 1, n)
	A[0] += 1
	A[r1] -= 1
	A[i + 1] += 1
	A[r2] -= 1
for i in range(n):
	A[i + 1] += A[i]
print(A.index(max(A)) + 1)


N = int(input().strip())
T = [int(var) for var in input().strip().split()]
finishes = [0] * N
for i in range(N):
	if T[i] > 0 and T[i] < N:
		finishes[(i + 1 - T[i]) % N] -= 1
		finishes[(i + 1) % N] += 1
maxNum = finishes[0]
idx = 0
acc = finishes[0]
for i in range(1, N):
	acc += finishes[i]
	if acc > maxNum:
		idx = i
		maxNum = acc
print(idx + 1)


m = int(input().strip())
ts = [int(x) for x in input().strip().split(' ')]
ss = [t - n for (n, t) in enumerate(ts)]
diffpts = [0] * (m + 1)
for (n, s) in enumerate(ss):
	if ts[n] == 0 or ts[n] >= m:
		continue
	if s > 0:
		diffpts[n + 1] += 1
		diffpts[m - s + 1] -= 1
	else:
		diffpts[0] += 1
		diffpts[m] -= 1
		diffpts[-s + 1] -= 1
		diffpts[n + 1] += 1
(m, midx) = (-1, 0)
rm = 0
for (idx, cur) in enumerate(diffpts):
	rm += cur
	if rm > m:
		midx = idx
		m = rm
print(midx + 1)


import sys
import heapq
n = int(input().strip())
s = list(map(int, input().strip().split()))
t = 0
(a, b) = ([], [])
for i in range(n):
	s[i] = s[i] - i
	if s[i] <= 0:
		t += 1
		heapq.heappush(b, [-s[i], i])
m = t
mi = 0
for i in range(1, n):
	if s[i - 1] > -(i - 1):
		heapq.heappush(a, -s[i - 1])
		t += 1
	while a and a[0] < i - n:
		heapq.heappop(a)
		t -= 1
	while b and b[0][0] < i:
		if b[0][1] >= i:
			t -= 1
		heapq.heappop(b)
	if m < t:
		m = t
		mi = i
print(mi + 1)


n = int(input())
c = [-1] * n + [0] * n
for (i, a) in enumerate(map(int, input().split())):
	c[i + max(0, n - a)] += 1
for i in range(2 * n - 2, -1, -1):
	c[i] += c[i + 1]
print(1 + max(range(n), key=lambda x: c[x] + c[x + n]))


n = int(input())
students = [int(x) for x in input().split()]
finishstart = [0] * n
currtotal = 0
for i in range(0, n):
	if students[i] - i <= 0:
		currtotal += 1
	if students[i] == 0 or students[i] == n:
		continue
	finishstart[(i + 1) % n] += 1
	finishstart[(i - (students[i] - 1)) % n] -= 1
maxVal = currtotal
currmax = 0
for v in range(1, n):
	currtotal += finishstart[v]
	if currtotal > maxVal:
		maxVal = currtotal
		currmax = v
print(currmax + 1)


n = int(input())
A = [0] * (n + 1)
for (i, x) in enumerate(map(int, input().split())):
	r1 = max(-1, i - x) + 1
	r2 = min(max(i, i - x + n) + 1, n)
	A[0] += 1
	A[r1] -= 1
	A[i + 1] += 1
	A[r2] -= 1
for i in range(n):
	A[i + 1] += A[i]
print(A.index(max(A)) + 1)


n = int(input())
times = [int(x) for x in input().split(' ')]
res = [0] * n
for i in range(n):
	if 1 <= times[i] < n:
		res[(n + i + 1) % n] += 1
		res[(n + i - times[i] + 1) % n] -= 1
max_sum = -10000007
tmp = 0
val = -1
for i in range(n):
	tmp += res[i]
	if tmp > max_sum:
		max_sum = tmp
		val = i + 1
print(val)


n = int(input())
t = list(map(int, input().split(' ')))

def max_complete(n, t):
	heaviside = [0] * (n + 1)
	for (i, num) in enumerate(t):
		if t[i] <= n:
			lo = (i + 1) % n
			hi = (i - num) % n
			if hi < lo:
				heaviside[0] += 1
				heaviside[lo] += 1
			else:
				heaviside[lo] += 1
			heaviside[hi + 1] -= 1
	m_index = -1
	m_value = 0
	running = 0
	for (i, num) in enumerate(heaviside):
		running += num
		if running > m_value:
			m_index = i
			m_value = running
	return m_index + 1
print(max_complete(n, t))


import sys
from itertools import accumulate
n = int(input().strip())
T = [int(t) for t in input().strip().split(' ')]
S = [0] * n
for (i, t) in enumerate(T):
	if t == 0:
		continue
	(first, last) = (i + 1, i + 1 + n - t)
	S[first % n] += 1
	if first < n:
		S[0] += 1
	S[last % n] -= 1
S = list(accumulate(S))
print(max(enumerate(S), key=lambda s: s[1])[0] + 1)


n = int(input().strip())
ts = [int(i) for i in input().strip().split()]
cur_max = 0
cur_node = 0
running_max = 0
seen = set()
intervals = {}
index = -1
for (i, t) in enumerate(ts):
	start = i + 1
	stop = i - t + n
	if t == n:
		continue
	if start % n > stop % n or start % n == 0 or stop % n == 0:
		cur_max += 1
		cur_node += 1
		if stop % n != 0:
			seen.add(i + 1)
		else:
			cur_node -= 1
	if start % n not in intervals:
		intervals[start % n] = []
	if stop % n not in intervals:
		intervals[stop % n] = []
	intervals[start % n].append(i + 1)
	intervals[stop % n].append(-(i + 1))
running_max = cur_max
index = 1
for i in range(1, n):
	cur_max = cur_node
	if i in intervals:
		for bracket in intervals[i]:
			if bracket > 0:
				seen.add(bracket)
				cur_max += 1
				cur_node += 1
			else:
				seen.remove(-bracket)
				cur_node -= 1
		if cur_max > running_max:
			running_max = cur_max
			index = i + 1
print(index)


N = int(input())
diff_list = [0] * (2 * N + 1)
for (i, t) in enumerate(map(int, input().strip().split()), N):
	if t > 0:
		diff_list[i - (t - 1)] -= 1
		diff_list[i + 1] += 1
for i in range(1, 2 * N + 1):
	diff_list[i] += diff_list[i - 1]
for i in range(N):
	diff_list[i] += diff_list[i + N]
diff_list[0] += diff_list[2 * N]
(mx, mxid) = (-float('inf'), -1)
for i in range(N):
	if diff_list[i] > mx:
		mx = diff_list[i]
		mxid = i
print(mxid + 1)


n = int(input())
A = [0] * (n + 1)
for (i, x) in enumerate(map(int, input().split())):
	r1 = max(-1, i - x) + 1
	r2 = min(max(i, i - x + n) + 1, n)
	A[0] += 1
	A[r1] -= 1
	A[i + 1] += 1
	A[r2] -= 1
for i in range(n):
	A[i + 1] += A[i]
print(A.index(max(A)) + 1)


n = int(input())
newpasses = [0] * n
timeneeded = [int(num) for num in input().split()]
for i in range(n):
	t = timeneeded[i]
	p = (i + 1) % n
	f = (i + 1 - t) % n
	newpasses[p] += 1
	newpasses[f] -= 1
besti = 0
bestvalue = newpasses[0]
passes = 0
for i in range(n):
	passes += newpasses[i]
	if passes > bestvalue:
		bestvalue = passes
		besti = i
print(besti + 1)


n = int(input())
students = [int(x) for x in input().strip().split(' ')]
intervals = [0 for i in students]
for (i, s) in enumerate(students):
	if s > n or s == 0:
		continue
	intervals[(i + 1) % n] += 1
	intervals[(i - (s - 1) + n) % n] -= 1
rsum = 0
maxSum = -1000000000
resultIndex = 0
for (index, i) in enumerate(intervals):
	rsum += i
	if rsum > maxSum:
		maxSum = rsum
		resultIndex = index + 1
print(resultIndex)


n = int(input())
A = map(int, input().split())
intervals = []
for (i, t) in enumerate(A):
	if t > 0 and t < n:
		intervals.append((i - t if i >= t else n + (i - t), -1))
		intervals.append((i + 1 if i + 1 < n else 0, 1))
intervals.sort(key=lambda e: (e[0], -e[1]))
max_v = 0
max_i = 0
v = 0
for interval in intervals:
	v += interval[1]
	if v > max_v:
		max_i = interval[0]
		max_v = v
print(max_i + 1)


from collections import defaultdict
size = int(input())
can_finish = defaultdict(lambda : 0)
ns = list(map(int, input().split()))
for (i, n) in enumerate(ns):
	can_finish[(i + 1) % size] += 1
	can_finish[(i - n + 1) % size] -= 1
most_finished = 0
most_finished_index = 0
finished_so_far = 0
for (k, v) in can_finish.items():
	finished_so_far += v
	if finished_so_far > most_finished:
		most_finished = finished_so_far
		most_finished_index = k
print(most_finished_index + 1)


import sys
import collections
n = int(sys.stdin.readline())
t = [int(i) for i in sys.stdin.readline().split(' ')]
sign_list = [0] * n
for i in range(len(t)):
	if 0 < t[i] < n:
		sign_list[(i + 1) % n] += 1
		sign_list[(i + n - (t[i] - 1)) % n] -= 1
finish_num = 0
max_finish_num = sign_list[0]
res = 0
for i in range(len(sign_list)):
	if sign_list[i]:
		finish_num += sign_list[i]
		if finish_num > max_finish_num:
			res = i
			max_finish_num = finish_num
res += 1
print(res)


n = int(input())
t = [int(i) for i in input().split(' ')]
finished = [0 for i in range(n)]
for i in range(n):
	if t[i] == 0 or t[i] == n:
		continue
	plus = (i + 1) % n
	minus = (i - t[i] + 1) % n
	finished[plus] += 1
	finished[minus] -= 1
for i in range(1, n):
	finished[i] += finished[i - 1]
print(finished.index(max(finished)) + 1)


n = int(input())
A = [0] * (n + 1)
for (i, x) in enumerate(map(int, input().split())):
	r1 = max(-1, i - x) + 1
	r2 = min(max(i, i - x + n) + 1, n)
	A[0] += 1
	A[r1] -= 1
	A[i + 1] += 1
	A[r2] -= 1
for i in range(n):
	A[i + 1] += A[i]
print(A.index(max(A)) + 1)


n = int(input())
T = list(map(int, input().split()))
from operator import add
from itertools import accumulate

def findx(N, T):
	T = T * 2
	levels = [0] * (2 * N)
	for x in range(N):
		t = T[x]
		if t < N and t > 0:
			levels[x + 1] += 1
			levels[x + N - t + 1] -= 1
	levels = accumulate(map(add, levels[:N], levels[N:]))
	x = 0
	best = float('-inf')
	bestx = 'wtf?'
	for level in levels:
		x += 1
		if level > best:
			best = level
			bestx = x
	return bestx
print(findx(n, T))


import operator
n = int(input().strip())
times = [int(x) for x in input().strip().split()]
ranges = []
events = []
for (i, time) in enumerate(times):
	if time == n:
		continue
	events.append((i + 1, True))
	events.append(((i - times[i] + 1) % n, False))
	ranges.append((i + 1, (i - times[i] + 1) % n))
events = sorted(events, key=operator.itemgetter(0))
count = 0
for (start, end) in ranges:
	if start == 0 or (end > 0 and end < start):
		count += 1
max_students = (count, 0)
idx = 0
while events[idx][0] <= 0:
	idx += 1
i = 1
while i < n:
	new_start = 0
	new_end = 0
	while events[idx][0] <= i:
		if events[idx][1]:
			new_start += 1
		else:
			new_end += 1
		idx += 1
	count += new_start
	count -= new_end
	if count > max_students[0]:
		max_students = (count, i)
	i += 1
print(max_students[1] + 1)


n = int(input().strip())
t = [int(arr_temp) for arr_temp in input().strip().split(' ')]
start_counts = {}
for i in range(n):
	extra_time = t[i] - i
	if extra_time <= 0:
		start_counts[extra_time] = start_counts.get(extra_time, 0) + 1
cur_score = sum(start_counts.values())
best_score = cur_score
best_index = 0
for j in range(n - 1):
	cur_elem_place = t[j] - j
	if cur_elem_place - n < -j:
		start_counts[cur_elem_place - n] = start_counts.get(cur_elem_place - n, 0) + 1
		cur_score += 1
	if -j in start_counts:
		cur_score -= start_counts[-j]
		del start_counts[-j]
	if cur_score > best_score:
		best_score = cur_score
		best_index = j + 1
print(best_index + 1)


import sys
import random

def smart2(r):
	n = len(r)
	c = {}
	cnt = 0
	for i in range(0, n):
		if r[i] <= 0:
			cnt = cnt + 1
			continue
		if r[i] >= n:
			continue
		if r[i] <= i:
			cnt = cnt + 1
			c[i - r[i]] = c.get(i - r[i], 0) - 1
		c[i] = c.get(i, 0) + 1
		passed = (i - r[i]) % n
		if passed > i:
			c[passed] = c.get(passed, 0) - 1
	maxCnt = cnt
	imax = 0
	for i in range(0, n - 1):
		if cnt > maxCnt:
			maxCnt = cnt
			imax = i
		cnt = cnt + c.get(i, 0)
	return imax + 1
lines = sys.stdin.readlines()
remainders = [int(x) for x in lines[1].split(' ')]
print(smart2(remainders))


n = int(input())
T = [int(x) for x in input().split()]
finish = [0] * n
done = 0
for i in range(n):
	t = T[i]
	if t < n:
		finish[i] += 1
		finish[(i - t) % n] -= 1
	if t <= i:
		done += 1
best = done
best_i = 0
for i in range(n):
	if done > best:
		best = done
		best_i = i
	done += finish[i]
print(best_i + 1)


num_students = int(input())
timing = [int(x) for x in input().split(' ')]
sub_counts = [0] * 10
counts = [0] * num_students
for (ndx, t) in enumerate(timing):
	if t == 0:
		counts[0] += 1
	elif t <= ndx:
		counts[0] += 1
		counts[ndx - (t - 1)] -= 1
		if ndx + 1 < len(timing):
			counts[ndx + 1] += 1
	else:
		pos = len(counts) - (t - ndx)
		if pos > ndx + 1:
			counts[ndx + 1] += 1
			if pos + 1 < len(counts):
				counts[pos + 1] -= 1
m = counts[0]
m_ndx = 0
for ndx in range(1, len(counts)):
	counts[ndx] = counts[ndx] + counts[ndx - 1]
	if counts[ndx] > m:
		m = counts[ndx]
		m_ndx = ndx
print(m_ndx + 1)


n = int(input())
A = [0] * (n + 1)
for (i, x) in enumerate(map(int, input().split())):
	r1 = max(-1, i - x) + 1
	r2 = min(max(i, i - x + n) + 1, n)
	A[0] += 1
	A[r1] -= 1
	A[i + 1] += 1
	A[r2] -= 1
for i in range(n):
	A[i + 1] += A[i]
print(A.index(max(A)) + 1)


n = int(input())
tArray = list(map(lambda x: int(x), input().split(' ')))
accum = [0] * n
for i in range(n):
	if tArray[i] == 0:
		accum[0] += 1
	elif tArray[i] != n:
		end = i - tArray[i] + 1
		start = i + 1
		if start < n:
			accum[start] += 1
			if end >= 0:
				accum[0] += 1
		elif start == n:
			accum[0] += 1
		else:
			raise ValueError("start shouldn't be more than n")
		accum[end] -= 1
numSucc = [accum[i] for i in range(n)]
for i in range(n):
	if i > 0:
		numSucc[i] = numSucc[i] + numSucc[i - 1]
maxSucc = max(numSucc)
for i in range(n):
	if numSucc[i] == maxSucc:
		print(i + 1)
		break


N = int(input().strip())
finishMap = [0] * (N + 1)
time = [int(x) for x in input().strip().split(' ')]
for (i, t) in enumerate(time):
	if t == 0 or t == N:
		continue
	sid = i + 1
	if sid == N:
		finishMap[0] += 1
	else:
		finishMap[sid + 1] += 1
	idx = 0
	if t > sid:
		idx = N - (t - sid) + 1
	else:
		idx = sid - t + 1
	finishMap[idx] -= 1
(maxCnt, maxIdx, sum) = (finishMap[1], 1, 0)
for i in range(1, N + 1):
	sum += finishMap[i]
	if sum > maxCnt:
		maxCnt = sum
		maxIdx = i
print(maxIdx)


n = int(input())
A = [0] * (n + 1)
for (i, x) in enumerate(map(int, input().split())):
	r1 = max(-1, i - x) + 1
	r2 = min(max(i, i - x + n) + 1, n)
	A[0] += 1
	A[r1] -= 1
	A[i + 1] += 1
	A[r2] -= 1
for i in range(n):
	A[i + 1] += A[i]
print(A.index(max(A)) + 1)


N = int(input())
d = dict()
xs = map(int, input().split())
for (i, x) in enumerate(xs):
	if x != 0 and x < N:
		bad = (i + 1 - x) % N
		good = (i + 1) % N
		if bad in d:
			d[bad] -= 1
		else:
			d[bad] = -1
		if good in d:
			d[good] += 1
		else:
			d[good] = 1
		if bad < good:
			if 0 in d:
				d[0] += 1
			else:
				d[0] = 1
m = -1e+100
m_i = 1
s = 0
for k in sorted(d):
	s += d[k]
	if s > m:
		m = s
		m_i = k + 1
print(m_i)


n = int(input())
times = [int(i) for i in input().split(' ')]
nets = [0] * n
for i in range(n):
	if times[i] >= 1 and times[i] <= n - 1:
		nets[(i - times[i] + 1) % n] -= 1
		nets[(i + 1) % n] += 1
mi = 0
finished = nets[0]
tf = finished
for i in range(1, n):
	tf += nets[i]
	if tf > finished:
		mi = i
		finished = tf
print(mi + 1)


n = int(input())
A = [0] * (n + 1)
for (i, x) in enumerate(map(int, input().split())):
	r1 = max(-1, i - x) + 1
	r2 = min(max(i, i - x + n) + 1, n)
	A[0] += 1
	A[r1] -= 1
	A[i + 1] += 1
	A[r2] -= 1
for i in range(n):
	A[i + 1] += A[i]
print(A.index(max(A)) + 1)


stuNum = int(input())
stuExtra = [int(x) for x in input().split()]
intervals = [[0, 0] for i in range(stuNum)]
for i in range(stuNum):
	if stuExtra[i] == 0 or stuExtra[i] >= stuNum:
		continue
	a = (i + 1) % stuNum
	b = (i - stuExtra[i] + stuNum) % stuNum
	intervals[a][0] += 1
	intervals[b][1] += 1
curOverlap = 0
maxSofar = 0
maxIndex = 0
for i in range(stuNum):
	curOverlap += intervals[i][0]
	if curOverlap > maxSofar:
		(maxSofar, maxIndex) = (curOverlap, i)
	curOverlap -= intervals[i][1]
print(maxIndex + 1)


n = int(input())
ts = [int(x) for x in input().split()]
students = [0 for _ in ts]
ok = []
notok = []
count = 0
for i in range(n):
	if ts[i] <= i:
		ok.append(i)
		count += 1
	else:
		notok.append(i)
res = count
added = [0 for _ in range(n + 1)]
for student in ok:
	added[student - ts[student] + 1] -= 1
	added[student + 1] += 1
for student in notok:
	added[n + student - ts[student] + 1] -= 1
	added[student + 1] += 1
resi = 0
for i in range(1, n):
	count += added[i]
	if res < count:
		res = count
		resi = i
print(resi + 1)


N = int(input())
t_students = [int(t) for t in input().split(' ')]
n_list = [0] * N
for i in range(0, N):
	if t_students[i] > 0 and t_students[i] < N:
		start = i + 1
		end = i - t_students[i] + N + 1
		n_list[start % N] += 1
		n_list[end % N] -= 1
maximum = -1
position = -1
running = 0
for i in range(0, N):
	running += n_list[i]
	if running > maximum:
		maximum = running
		position = i + 1
print(position)


import sys
n = int(sys.stdin.readline())
t = [int(x) for x in sys.stdin.readline().split()]
assert n == len(t)
initial_num_complete = 0
for (i, t_i) in enumerate(t):
	if t_i <= i:
		initial_num_complete += 1
deltas = [0] * n
for (i, t_i) in enumerate(t):
	if t_i >= n or t_i <= 0:
		continue
	deltas[(i + 1) % n] += 1
	deltas[(i + n - t_i + 1) % n] -= 1
assert sum(deltas) == 0
(max_i, num_complete, max_num_complete) = (0, initial_num_complete, initial_num_complete)
for i in range(1, n):
	num_complete += deltas[i]
	if num_complete > max_num_complete:
		(max_i, max_num_complete) = (i, num_complete)
print(max_i + 1)


tamanio = int(input())
tiempos = [int(i) for i in input().split()]
casillas_prohibidas = [[] for i in range(tamanio)]
contador = [0 for i in range(tamanio)]
for i in range(tamanio):
	if tiempos[i] != 0 and tiempos[i] != tamanio:
		casillas_prohibidas[(i + 1 - tiempos[i]) % tamanio] += [i]
conjunto = set([])
for i in range(tamanio):
	conjunto -= conjunto & set(casillas_prohibidas[i])
	contador[i] += len(conjunto)
	if tiempos[i] != 0 and tiempos[i] != tamanio:
		conjunto |= set([i])
pos = 0
while len(conjunto) != 0:
	conjunto -= conjunto & set(casillas_prohibidas[pos])
	contador[pos] += len(conjunto)
	pos += 1
maximo = 0
for i in range(tamanio):
	if contador[i] > maximo:
		maximo = contador[i]
		pos = i
print(pos + 1)


n = int(input())
times = []
times = list(map(int, input().split()))
answer = [0] * n
for i in range(n):
	val = times[i]
	new = i - val
	if val == 0:
		answer[0] += 1
	elif val >= n:
		pass
	elif new < 0:
		new1 = n + new
		if i + 1 < n:
			answer[i + 1] += 1
		if new1 + 1 < n:
			answer[new1 + 1] -= 1
	elif new >= 0:
		answer[0] += 1
		answer[new + 1] -= 1
		if i + 1 < n:
			answer[i + 1] += 1
max1 = 0
index = 0
total = 0
for i in range(n):
	total += answer[i]
	if total > max1:
		index = i
		max1 = total
print(index + 1)


import sys
n = int(input().strip())
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]

def get_init_count(arr):
	count = 0
	for i in range(len(arr)):
		if i < arr[i]:
			count += 1
	return count

def calc_starts(starts, arr):
	for i in range(len(arr)):
		locn = i - arr[i]
		if locn < 0:
			locn += len(arr)
		starts[locn] += 1
init = len(arr) - get_init_count(arr)
starts = [0] * len(arr)
calc_starts(starts, arr)
mx = init
c = init
idx = 0
for i in range(1, len(arr)):
	c = c - starts[i - 1] + 1
	if c > mx:
		mx = c
		idx = i
print(idx + 1)


size = int(input())
students = [int(i) for i in input().split(' ')]
finished = []

def finish_turning_point(start, time):
	if time == 0:
		return 0
	return (1 + (start - time)) % size

def not_turning_point(start, time):
	if time == 0:
		return 0
	return (start + 1) % size
net = [0] * size
for start in range(size):
	time = students[start]
	net[finish_turning_point(start, time)] -= 1
	net[not_turning_point(start, time)] += 1
maxi = 0
maxi_value = net[0]
running = 0
for i in range(len(net)):
	running += net[i]
	if running > maxi_value:
		maxi = i
		maxi_value = running
print(maxi + 1)


import sys
n = int(input())
c = [-1] * n + [0] * n
for (i, a) in enumerate(input().split()):
	c[i + max(0, n - int(a))] += 1
for i in range(2 * n - 2, -1, -1):
	c[i] += c[i + 1]
print(1 + max(range(n), key=lambda x: c[x] + c[x + n]))


from itertools import accumulate
n = int(input())
l = [int(s) for s in input().split()]
t = [0 for _ in range(n)]
for (i, v) in enumerate(l):
	if v == 0:
		t[0] += 1
	elif v < n:
		if i + 1 < n:
			t[i + 1] += 1
			if i + 1 + n - v < n:
				t[i + 1 + n - v] -= 1
		if i >= v:
			t[0] += 1
			t[i - v + 1] -= 1
c = list(accumulate(t))
print(c.index(max(c)) + 1)


n = int(input())
data = list(map(int, input().split()))
s = [0] * (n + 1)
for (i, x) in enumerate(data):
	if x < n:
		idx = (i + n - x) % n
		if idx <= i:
			s[0] += 1
			s[idx + 1] -= 1
			s[i + 1] += 1
		else:
			s[i + 1] += 1
			s[idx + 1] -= 1
for i in range(1, n + 1):
	s[i] += s[i - 1]
k = max(s)
print(min([i + 1 for i in range(n) if s[i] == k]))


total_students = int(input())
time_remaining = [int(student) for student in input().split()]

def get_completed_from_position(position):
	time = 0
	completed = 0
	while time < total_students:
		if time_remaining[position] <= time:
			completed += 1
		time += 1
		position = (position + 1) % total_students
	return completed

def get_best_position():
	best_position = 0
	most_completed = 0
	for position in range(total_students):
		completed = get_completed_from_position(position)
		if completed > most_completed:
			best_position = position
			most_completed = completed
	return best_position

def get_anti_score():
	loss_score = [0] * total_students
	for (position, time) in enumerate(time_remaining):
		if time >= total_students:
			continue
		if time > total_students - time:
			for x in range(total_students - time):
				loss_score[(position + x + 1) % total_students] -= 1
		else:
			for x in range(time):
				loss_score[(position - x) % total_students] += 1
	return loss_score

def get_min_score(scores):
	min_score = scores[0]
	best_position = 0
	for (position, score) in enumerate(scores):
		if score < min_score:
			min_score = score
			best_position = position
	return best_position

def get_transitions():
	transitions = [0] * total_students
	for (position, time) in enumerate(time_remaining):
		if time >= total_students or time == 0:
			continue
		transitions[(position + 1) % total_students] += 1
		transitions[(position - time + 1) % total_students] -= 1
	return transitions

def get_best_transition(transitions):
	score = 0
	best_score = transitions[0]
	best_position = 0
	running_sums = []
	for (position, transition) in enumerate(transitions):
		next_score = score + transition
		running_sums.append(next_score)
		if next_score > best_score:
			best_position = position
			best_score = next_score
		score = next_score
	return best_position
transitions = get_transitions()
best_position = get_best_transition(transitions)
print(best_position + 1)


n = int(input().strip())
arr = list(map(int, input().strip().split()))
from collections import defaultdict
c = defaultdict(int)
for i in range(n):
	c[i] -= 1
	c[i + max(0, n - arr[i])] += 1
for i in range(2 * n - 2, -1, -1):
	c[i] += c[i + 1]
ans = ansx = -1
for x in range(n):
	t = c[x] + c[x + n]
	if ans < t:
		ans = t
		ansx = x
print(ansx + 1)


from itertools import accumulate

def best_start_idx(n, t):
	d = [0] * n
	for i in range(n):
		if 0 < t[i] < n:
			d[(i + 1 - t[i]) % n] -= 1
			d[(i + 1) % n] += 1
	(max_drawings, idx) = max(((r, -i) for (i, r) in enumerate(accumulate(d))))
	return -idx + 1
n = int(input().strip())
ar = list(map(int, input().strip().split(' ')))
print(best_start_idx(n, ar))


import sys

def pickStart(n, arr):
	indexes = [0] * n
	for i in range(n):
		if arr[i] < n:
			goodStart = (n + i + 1) % n
			badStart = (n + i - arr[i] + 1) % n
			indexes[goodStart] += 1
			indexes[badStart] += -1
	sum = indexes[0]
	savedsum = indexes[0]
	index = 0
	for i in range(1, n):
		sum += indexes[i]
		if sum > savedsum:
			savedsum = sum
			index = i
	return str((index + 1) % n)
n = int(sys.stdin.readline())
ts = []
for t in sys.stdin.readline().split():
	ts.append(int(t))
sys.stdout.write(pickStart(n, ts))


n = int(input())
x = list(map(int, input().split(' ')))
l = len(x)
ans = [0] * l
for i in range(l):
	if x[i] == 0:
		continue
	elif x[i] >= l:
		continue
	else:
		j = x[i]
		ans[(i - j + 1) % l] -= 1
		ans[(i + 1) % l] += 1
maxn = -1
maxi = 0
count = 0
for i in range(l):
	count += ans[i]
	if count > maxn:
		maxn = count
		maxi = i
print(maxi + 1)


n = int(input())
times = list(map(int, input().split(' ')))
answer = [0] * n
for a in range(n):
	cur = times[a]
	cur = cur % n
	temp = a - cur + 1
	if temp < 0:
		temp = n + temp
		answer[0] += 1
	if temp == n:
		temp = 0
	answer[temp] += 1
	temp = a + 1
	if temp < n:
		answer[temp] -= 1
cur_answer = answer[0]
end_answer = answer[0]
to_print = 0
for a in range(1, n):
	cur_answer += answer[a]
	if cur_answer < end_answer:
		to_print = a
		cur_answer = end_answer
	if end_answer == 0:
		break
print(to_print + 1)


def getsum(BIT, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BIT[i]
		i -= i & -i
	return s

def updatebit(BIT, n, i, v):
	i += 1
	while i <= n:
		BIT[i] += v
		i += i & -i

def construct(arr, n):
	BIT = [0] * (n + 1)
	for i in range(n):
		updatebit(BIT, n, i, arr[i])
	return BIT

def main():
	n = int(input())
	str_list = input().split()
	init = [int(i) for i in str_list]
	bitree = construct([0] * (3 * n + 1), 3 * n + 1)
	for i in range(n):
		init[i] = i - init[i]
		updatebit(bitree, 3 * n, init[i] + n, 1)
	max_pos = 0
	max_nfin = getsum(bitree, 3 * n) - getsum(bitree, n - 1)
	for i in range(n - 1):
		updatebit(bitree, 3 * n, init[i] + n, -1)
		updatebit(bitree, 3 * n, init[i] + 2 * n, 1)
		nfin = getsum(bitree, 3 * n) - getsum(bitree, n + i)
		if nfin > max_nfin:
			max_nfin = nfin
			max_pos = i + 1
	print(max_pos + 1)
main()


def solve(n, ts):
	stuff = [0] * n
	for (idx, v) in enumerate(ts):
		if v == 0 or v == n:
			continue
		est = idx + 1
		if est == n:
			est = 0
		lst = (idx - v + 1) % n
		stuff[lst] -= 1
		stuff[est] += 1
	(maxi, idx, sumi) = (-1, -1, 0)
	for (i, v) in enumerate(stuff):
		sumi += v
		if sumi > maxi:
			maxi = sumi
			idx = i
	return idx + 1
n = int(input())
ts = [int(x) for x in input().split()]
result = solve(n, ts)
print(result)


import os
import sys
from collections import defaultdict
n = int(input())
t = list(map(int, input().rstrip().split()))

def getVotes(times):
	votes = []
	for i in range(len(times)):
		time = times[i]
		if time == 0 or time > len(times):
			continue
		votes.append(((i + 1) % len(times), (i - time + len(times)) % len(times)))
	return votes

def countVotes(votes):
	votedDiff = defaultdict(int)
	for (start, end) in votes:
		if end < start:
			end += len(t)
		votedDiff[start] += 1
		votedDiff[start + len(t)] += 1
		votedDiff[end + 1] -= 1
		votedDiff[end + len(t) + 1] -= 1
	currBestCount = 0
	currBestIndex = 2 * len(t)
	currVoteCount = 0
	for i in range(len(t) * 2):
		currVoteCount += votedDiff[i]
		if currVoteCount > currBestCount or (currVoteCount == currBestCount and i % len(t) < currBestIndex % len(t)):
			currBestIndex = i
			currBestCount = currVoteCount
	return currBestIndex % len(t)
print(countVotes(getVotes(t)) + 1)


import os
import sys
n = int(input())
t = list(map(int, input().rstrip().split()))
intervals = []
for i in range(n):
	if t[i] == 0:
		intervals.append((0, 0))
		intervals.append((n - 1, 1))
	elif t[i] < n:
		x = (i - t[i] + n) % n
		if x > i:
			intervals.append((i + 1, 0))
			intervals.append((x, 1))
		else:
			intervals.append((0, 0))
			intervals.append((x, 1))
			intervals.append((i + 1, 0))
			intervals.append((n - 1, 1))
intervals.sort()
mx = 0
ind = 0
interval_ind = 0
opened = 0
for i in range(n):
	while interval_ind < len(intervals) and intervals[interval_ind][0] == i:
		if intervals[interval_ind][1] == 0:
			opened += 1
			interval_ind += 1
			if opened > mx:
				mx = opened
				ind = i
		else:
			opened -= 1
			interval_ind += 1
print(ind + 1)