B. Чемпионат мира
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аллен хочет попасть в фан-зону, которая расположена на круглой площади и имеет $$$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$$$) — количество людей в очередях. В эти числа Аллен не включен.

Выходные данные

Выведите одно целое число — номер входа, которым в итоге воспользуется Аллен.

Примеры
Входные данные
4
2 3 2 0
Выходные данные
3
Входные данные
2
10 10
Выходные данные
1
Входные данные
6
5 2 6 5 7 4
Выходные данные
6
Примечание

В первом примере число людей (не включая Аллена) меняется так: $$$[\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}]$$$.