Allen wants to enter a fan zone that occupies a round square and has $n$ entrances.

There already is a queue of $a_i$ people in front of the $i$-th entrance. Each entrance allows one person from its queue to enter the fan zone in one minute.

Allen uses the following strategy to enter the fan zone:   Initially he stands in the end of the queue in front of the first entrance.  Each minute, if he is not allowed into the fan zone during the minute (meaning he is not the first in the queue), he leaves the current queue and stands in the end of the queue of the next entrance (or the first entrance if he leaves the last entrance). 

Determine the entrance through which Allen will finally enter the fan zone.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the number of entrances.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the number of people in queues. These numbers do not include Allen.


-----Output-----

Print a single integer — the number of entrance that Allen will use.


-----Examples-----
Input
4
2 3 2 0

Output
3

Input
2
10 10

Output
1

Input
6
5 2 6 5 7 4

Output
6



-----Note-----

In the first example the number of people (not including Allen) changes as follows: $[\textbf{2}, 3, 2, 0] \to [1, \textbf{2}, 1, 0] \to [0, 1, \textbf{0}, 0]$. The number in bold is the queue Alles stands in. We see that he will enter the fan zone through the third entrance.

In the second example the number of people (not including Allen) changes as follows: $[\textbf{10}, 10] \to [9, \textbf{9}] \to [\textbf{8}, 8] \to [7, \textbf{7}] \to [\textbf{6}, 6] \to \\ [5, \textbf{5}] \to [\textbf{4}, 4] \to [3, \textbf{3}] \to [\textbf{2}, 2] \to [1, \textbf{1}] \to [\textbf{0}, 0]$.

In the third example the number of people (not including Allen) changes as follows: $[\textbf{5}, 2, 6, 5, 7, 4] \to [4, \textbf{1}, 5, 4, 6, 3] \to [3, 0, \textbf{4}, 3, 5, 2] \to \\ [2, 0, 3, \textbf{2}, 4, 1] \to [1, 0, 2, 1, \textbf{3}, 0] \to [0, 0, 1, 0, 2, \textbf{0}]$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
mn = 10000000000
ans = -1
from math import ceil
for i in range(n):
    b = a[i] - i
    c = int(ceil(b / n))
    cc = n*c
    if n*c < mn:
        mn = n*c
        ans = i+1
print(ans)            

from math import ceil

n = int(input())
a = list(map(int, input().split()))

for i in range(n):
    a[i] -= i

for i in range(n):
    a[i] = ceil(a[i] / n)

ans = -1
s = 10 ** 9 + 7

for i in range(n):
    if a[i] < s:
        s = a[i]
        ans = i + 1

print(ans)


n=int(input())
ta=input().split()
a=[0]
for i in ta:
    a.append(int(i)+n)
mn=1000000000000000000
mner=1
for i in range(1,n+1):
    if (a[i]-i)//n<mn:
        mn=(a[i]-i)//n
        mner=i
print(mner)


n = int(input())

arr = list(map(int, input().split()))
m = int(1e12)
ans = 1

for i in range(n):
    k = arr[i] // n
    k *= n
    while (k +  i < arr[i]):
        k += n

    if k < m:
        m = min(m, k)
        ans = i
print(ans+1)


n = int(input())
a = list(map(int, input().split()))
m = a[0]
for i in range(n):
    m = min(m, a[i])
if (m == 0):
    ans = 1
    for i in range(n):
        if (a[i] - i <= 0):
            ans = i + 1
            break
    print(ans)
else:
    cur = m % n
    for i in range(cur, cur + n):
        d = i - cur
        i %= n
        if (a[i] - d - m <= 0):
            ans = i + 1
            break
    print(ans)

3

def solve(N, A):
    mn = min(A)
    if mn > N:
        A = [a - (mn // N * N) for a in A]

    decr = 0
    i = 0
    while True:
        if A[i] - decr <= 0:
            return i + 1

        decr += 1
        i += 1
        if i == N:
            i = 0


def main():
    N = int(input())
    A = [int(e) for e in input().split(' ')]
    assert len(A) == N
    print(solve(N, A))


def __starting_point():
    main()

__starting_point()

n = int(input())
arr = list(map(int, input().split()))
mi = arr[0]
ind = 0
for i in range(n):
    if(arr[i] < mi):
        mi = arr[i]
        ind = i
kol = mi
pol = kol % n
#print(kol, pol)
for i in range(n):
    #print(kol, arr[i])
    if(kol >= arr[pol]):
        break
    kol += 1
    pol = (pol + 1) % n
print(pol + 1)

#!/usr/bin/env python3
from sys import stdin


def solve(tc):
    n = int(stdin.readline().strip())
    li = list(map(int,stdin.readline().split()))

    ans = 1
    mini = 1e9
    for i in range(n):
        k = li[i] // n
        if li[i]%n>i:
            k += 1
        
        if k<mini:
            mini = k
            ans = i+1
    
    print(ans)



LOCAL_TEST = not __debug__
if LOCAL_TEST:
    infile = __file__.split('.')[0] + "-test.in"
    stdin = open(infile, 'r')

tcs = (int(stdin.readline().strip()) if LOCAL_TEST else 1)
tc = 1
while tc <= tcs:
    solve(tc)
    tc += 1

import math
n=int(input())
l=list(map(int,input().strip().split()))
l1=[]
for x,y in enumerate(l):
	if (y<x):
		m=0
	else:
		m=y-x
	l1.append(math.ceil(m/n))
min1=100000000000000
min2=1000000000000
for i in range(n):
	if l1[i]<min1:
		min1=l1[i]
		min2=i+1
print (min2)

n = int(input())
ai = list(map(int,input().split()))
ans = -1
for i in range(n):
    ai[i] -= (i)
    if ai[i] <= 0:
        ans = i+1
        break
if ans == -1:
    mini = 10**9
    for i in range(n):
        temp = ai[i] /  n
        if temp != int(temp):
            temp += 1
        if mini > int(temp):
            mini = int(temp)
            ans = i+1
print(ans)


n = int(input())
s = input().split(" ")
for i in range(n):
    s[i] = int(s[i])

round = 1000000000
for i in range(n):
    if round > s[i]//n:
        round = s[i]//n
for i in range(n):
    s[i] -= round*n

i = 0
time = 0
while (1):
    if s[i] <= time:
        break
    i = (i+1) % n
    time += 1

print(i+1)


input()
queue=list(map(int,input().split()))
t=len(queue)
base=min(queue)
minu=int(base/t)*t
while(queue[minu%t]>minu):
    minu+=1
print(minu%t+1) 

n = int(input())
a = [int(v) for v in input().split()]

a = [ai - i for i, ai in enumerate(a)]

minv = 100000000000000
mini = None

for i, ai in enumerate(a):
    if ai <= 0:
        print(i + 1)
        return
    else:
        v = (ai - 1) // n
        if v < minv:
            minv = v
            mini = i

print(mini + 1)


n=int(input())
arr=list(map(int,input().split()))
arrx=[]
for i in arr:
	arrx.append(i//n)
ans=0
arry=[]
for i in range(n):
	k=arrx[i]*n
	if(arr[i]-k<=i):
		k+=i+1
	else:
		k+=n+i+1
	arry.append(k)
#print(arry)
print(arry.index(min(arry))+1)

#!/usr/bin/env python3

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

def ceil(a, b):
	return -((-a) // b)

bis = [ceil(ai - i, n) for i, ai in enumerate(ais)]

bmin = min(bis)
ibmin = bis.index(bmin)

print(ibmin + 1)


from math import ceil
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=ceil((a[i]-i)/n)
mini=min(a)
print(a.index(mini)+1)

n = int(input())
data = list(map(int, input().split()))
ans = 1
ans_sum = (data[0] + n - 1) // n * n
for i in range(1, n):
    k = i + (data[i] - i + n - 1) // n * n
    if k < ans_sum:
        ans = i + 1
        ans_sum = k 
print(ans)

n = int(input())
a = list(map(int, input().split()))
s = min(a)
for q in range(n):
    a[q] -= s//n*n
q1 = 0
while a[q1 % n]-q1 > 0:
    q1 += 1
print(q1 % n+1)


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time
import math

n   = int(input())
a   = [int(i) for i in input().split()]

start = time.time()


min = math.ceil(a[0]/n)
mini = 0
for i in range(n):
    a[i] = math.ceil((a[i] - i)/n)
    if min > a[i]:
        mini = i
        min = a[i]

print(mini+1)
finish = time.time()
#print(finish - start)


while 1:
    try:
        n = int(input())
        a = [int(item) for item in input().split()]
        for i in range(n):
            tour = a[i] // n
            if i < a[i] % n:
                tour += 1
            a[i] = tour
        min_tour = float("inf")
        
        for i in range(n):
            if a[i] < min_tour:
                answer = i
                min_tour = a[i]
        print(answer + 1)
    except EOFError:
        break


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


n = int(input())
a=[int(_) for _ in input().strip().split()]

mini=min(a)
a=[_-mini for _ in a]
pos = mini%n
count = 0
while True:
	if a[pos] - count <=0:
		print(pos+1)
		break
	else:
		count+=1
		pos=(pos+1)%n

n = int(input())
arr = list(map(int, input().split()))
mn = min(arr)
# arr = [i - mn for i in arr]
pos = mn % n
val = mn
for _ in range(n):
    if arr[pos] <= val:
        ans = pos
        break
    pos = (pos + 1) % n
    val += 1
print(ans + 1)


import math
n = int(input().strip())
a=[int(x) for x in input().strip().split(' ')]
minm = 1000000000000000000
ans = 0
for i in range(n):
    v=a[i]-i
    if max(0,v)==0:
        if 0<minm:
            ans = i+1
            minm=0
    else:
        b = round(math.ceil(v/n)+1)
        if b<minm:
            ans = i+1
            minm=b
print(ans)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = [(i + 1, a[i] - i) for i in range(n)]
    a.sort(key = lambda b: (b[1] - 1) // n)
    a = list([b for b in a if (b[1] - 1) // n == (a[0][1] - 1) // n])
    a.sort(key = lambda b: b[0])
    print(a[0][0])
    return 0
main()