← 返回题目列表

Codeforces · 996/B

B. 世界杯

中文机器翻译题面 查看原题

艾伦想要进入一个占据圆形广场并有 $$$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}]$$$。