28583번 - Еще более защищенная тюрьма 스페셜 저지다국어

문제

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

Наборная панель таких замков представляет собой вращающийся диск с $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$).

출력

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

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

제한

힌트