Еще более защищенная тюрьма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После побега Клетуса Кэседи из тюрьмы Сан Квентин, служба охраны решила не только построить камеру особо строгого режима, но и модернизировать системы защиты, в частности, установить новые кодовые замки.

Наборная панель таких замков представляет собой вращающийся диск с $$$n$$$ сегментами, в $$$i$$$-м из которых находится целое положительное число $$$a_i$$$. Последовательность, написанная на диске, читается по часовой стрелке, начиная с сегмента, смотрящего строго вверх. Вращение диска осуществляется следующим образом: при нажатии на $$$i$$$-й (по часовой стрелке, начиная отсчет с верхнего) сегмент, диск поворачивается на $$$a_i$$$ сегментов против часовой стрелки, а сам нажатый сегмент блокируется и больше не является частью последовательности.

Пока система только устанавливается и настраивается, поэтому стандартный пароль никто не менял — когда последовательность на диске лексикографически минимальна среди всех, которые можно получить одним нажатием на некоторый сегмент, дверь открывается. Например, если на диске сейчас находится последовательность $$$a = [4, 3, 1, 2, 1, 8]$$$, при нажатии на $$$a_4 = 2$$$, диск поворачивается на $$$2$$$ против часовой стрелки, переходя в состояние $$$a = [1, 2, 1, 8, 4, 3]$$$, после чего нажатый сегмент блокируется, и итоговая последовательность будет равна $$$[1, 1, 8, 4, 3]$$$.

Напоминаем, что последовательность $$$x_1, x_2, \ldots, x_t$$$ лексикографически меньше последовательности $$$y_1, y_2, \ldots, y_t$$$, если существует такое $$$0 \leqslant k \leqslant t$$$, что $$$x_i = y_i$$$ для всех $$$i < k$$$, и $$$x_k < y_k$$$. То есть если первые их несколько элементов (возможно, ноль) совпадают, а следующий за этим элемент последовательности $$$x$$$ меньше соответствующего элемента $$$y$$$.

К сожалению, для охранников даже система по умолчанию достаточно сложная, и теперь они не могут покинуть территорию тюрьмы, пока не откроют находящуюся перед ними дверь. Помогите им в этом!

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

В первой строке ввода дано единственное целое число $$$n$$$ — количество сегментов на диске ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$).

В следующей строке через пробел перечислены $$$n$$$ чисел $$$a_i$$$ — числа, написанные на сегментах, в порядке по часовой стрелке, начиная с верхнего ($$$0 \leqslant a_i < n$$$).

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

Выведите единственное целое число — номер сегмента, на который надо нажать, чтобы последовательность после поворота стала лексикографически минимальной.

Если ответов несколько, выведите любой.

Примеры

Входные данные
4
1 2 3 3
Выходные данные
4
Входные данные
4
1 1 1 1
Выходные данные
1
Входные данные
4
1 2 1 2
Выходные данные
4