艾伦想要进入一个占据圆形广场并有 $$$n$$$ 入口的粉丝区。
第 $$$i$$$ 个入口前已经排起了 $$$a_i$$$ 人的队列。每个入口允许队列中的一个人在一分钟内进入球迷区。
艾伦使用以下策略进入粉丝区:
- 最初他站在第一个入口前队列的末尾。
- 每分钟,如果他在该分钟内不被允许进入球迷区(意味着他不是队列中的第一个),他会离开当前队列并站在下一个入口(如果他离开最后一个入口,则为第一个入口)的队列末尾。
确定艾伦最终进入粉丝区的入口。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 入口数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 队列中的人数。这些数字不包括艾伦。
输出
打印一个整数——艾伦将使用的入口号。
示例
输入 #1
4 2 3 2 0
输出 #1
3
输入 #2
2 10 10
输出 #2
1
输入 #3
6 5 2 6 5 7 4
输出 #3
6
注意
在第一个示例中,人数(不包括 Allen)变化如下:$$$[\textbf{2}, 3, 2, 0] \to [1, \textbf{2}, 1, 0] \to [0, 1, \textbf{0}, 0]$$$。粗体数字是阿莱斯所站的队列。我们看到他将从第三个入口进入球迷区。
在第二个示例中,人数(不包括 Allen)变化如下: $$$[\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] \到 [3, \textbf{3}] \到 [\textbf{2}, 2] \到 [1, \textbf{1}] \到 [\textbf{0}, 0]$$$。
在第三个示例中,人数(不包括 Allen)变化如下: $$$[\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] \到 [1, 0, 2, 1, \textbf{3}, 0] \到 [0, 0, 1, 0, 2, \textbf{0}]$$$。