human
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 ≤ n ≤ 10^5) — the number of entrances.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 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: [2, 3, 2, 0] → [1, 2, 1, 0] → [0, 1, 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: [10, 10] → [9, 9] → [8, 8] → [7, 7] → [6, 6] → \\\ [5, 5] → [4, 4] → [3, 3] → [2, 2] → [1, 1] → [0, 0].

In the third example the number of people (not including Allen) changes as follows: [5, 2, 6, 5, 7, 4] → [4, 1, 5, 4, 6, 3] → [3, 0, 4, 3, 5, 2] → \\\ [2, 0, 3, 2, 4, 1] → [1, 0, 2, 1, 3, 0] → [0, 0, 1, 0, 2, 0].
Solve the task in PYTHON3.

=====
What is a Python code to determine the entrance through which Allen will finally enter the fan zone?
assistant
#Here is Python code to determine the entrance through which Allen will finally enter the fan zone.

"""
    Author - Satwik Tiwari .
    13th NOV , 2020  - Friday
"""

#===============================================================================================
#importing some useful libraries.

from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key

# from itertools import *
from heapq import *
from math import gcd, factorial,floor,ceil,sqrt

from copy import deepcopy
from collections import deque

from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect

#==============================================================================================
#fast I/O region
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable =...