Джерри получил в пользование перестановку целых чисел от $$$1$$$ до $$$n$$$. К его большому сожалению, перестановку успел перед этим «улучшить» Рик, и теперь она постоянно находится в поисках лучшей версией себя, и Джерри это пугает.
Будем считать перестановку $$$a$$$ тем более хорошей, чем меньше в ней инверсий, то есть пар индексов $$$i < j$$$, для которых $$$a_i > a_j$$$. В поисках самой хорошей версии себя, перестановка каждую секунду циклически сдвигается на $$$1$$$ влево, то есть превращается в $$$$$$a^{\gets 1} = [a_2, a_3, \ldots, a_n, a_1] \text{.}$$$$$$
Определите, через сколько секунд перестановка превратится в лучшую версию себя, то есть станет содержать минимальное число инверсий.
В первой строке ввода дано целое число $$$n$$$ — длина перестановки ($$$1 \le n \le 2 \cdot 10^5$$$).
Во второй строке через пробел перечислены $$$n$$$ различных целых чисел $$$a_i$$$ — элементы текущей перестановки ($$$1 \le a_i \le n$$$).
Выведите единственное целое число — количество секунд, через которое перестановка будет содержать минимальное возможное число инверсий. Если возможных ответов несколько, выведите любой из них, меньший $$$n$$$.
3 2 1 3
0
5 5 3 4 2 1
3