CF996B.World Cup

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.

艾伦想要进入一个占据圆形广场的球迷区，该球迷区共有 $n$ 个入口。

第 $i$ 个入口前已排有 $a_i$ 个人的队伍。每个入口每分钟允许其队列中的一个人进入球迷区。

艾伦采用以下策略进入球迷区：

• 初始时，他站在第一个入口前队伍的末尾。
• 每分钟，如果他在该分钟内未被允许进入球迷区（即他不是队列中的第一个人），他就离开当前队列，并站到下一个入口队列的末尾（若他离开的是最后一个入口，则下一个入口为第一个入口）。

请确定艾伦最终进入球迷区时所通过的入口编号。

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.

第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— 表示入口的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）—— 表示各队列中的人数。这些数字不包括 Allen。

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

输出一个整数——Allen 将使用的入口编号。

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}]$.

在第一个例子中，人数（不包括艾伦）的变化过程如下：$[\textbf{2}, 3, 2, 0] \to [1, \textbf{2}, 1, 0] \to [0, 1, \textbf{0}, 0]$。加粗的数字表示艾伦当前所在的队列。可以看出，他将通过第三个入口进入球迷区。

在第二个例子中，人数（不包括艾伦）的变化过程如下：$[\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]$。

在第三个例子中，人数（不包括艾伦）的变化过程如下：$[\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}]$。