Even More Secure Prison

After Cletus Kasady escaped from the San Quentin prison, the guards decided to build a maximum security cell and upgrade the security systems, including installing new combination locks.

The dial of such a lock is a rotating disk with $n$ segments. The $i$-th segment contains a positive integer $a_i$. The sequence written on the disk is read clockwise, starting from the segment that points straight up. When you press the $i$-th segment (counting clockwise from the top), the disk turns $a_i$ segments counterclockwise, and the pressed segment is locked and is no longer part of the sequence.

For example, if the disk currently holds $a = [4, 3, 1, 2, 1, 8]$ and you press $a_4 = 2$, the disk turns 2 segments counterclockwise into the state $[1, 2, 1, 8, 4, 3]$. Then the pressed segment is locked, and the resulting sequence is $[1, 1, 8, 4, 3]$.

A sequence $x_1, x_2, \ldots, x_t$ is lexicographically smaller than $y_1, y_2, \ldots, y_t$ if there is a $0 \le k \le t$ such that $x_i = y_i$ for all $i < k$ and $x_k < y_k$. In other words, the first few elements (possibly none) are equal, and the next element of $x$ is smaller than the corresponding element of $y$.

The door opens when the sequence on the disk is lexicographically minimal among all sequences that can be obtained by pressing one segment. Find the segment to press.

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$), the number of segments on the disk. The second line contains $n$ integers $a_i$ ($0 \le a_i < n$), separated by spaces, in clockwise order starting from the top.

Print a single integer, the number of the segment to press so that the resulting sequence is lexicographically minimal. If there are several answers, print any of them.