После побега Клетуса Кэседи из тюрьмы Сан Квентин, служба охраны решила не только построить камеру особо строгого режима, но и модернизировать системы защиты, в частности, установить новые кодовые замки.
Наборная панель таких замков представляет собой вращающийся диск с $$$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