В казино «Ставки на раунды» часто играют в Сортджек. Это особая игра, для которой нужна особая колода из $n$ карт, не имеющих мастей, и пронумерованных от $1$ до $n$. $n$ всегда чётно.

Чтобы лучше тусовать колоды для игры, казино приобрело специального робота-дилера. Он умеет делать операцию перемешивания: взять колоду, разделить её ровно пополам посередине, а затем расположить карты из них «через одну», начиная со второй половины.

Например, если загрузить в робота колоду $[1, 2, 3, 4 \dots n]$, то после одной такой операции получится колода $[\frac{n}{2} + 1, 1, \frac{n}{2} + 2, 2, \dots, n, \frac{n}{2}]$. Чтобы колода перемешалась лучше, робот может повторить это действие любое заданное число раз.

Чтобы покрыть расходы на робота, казино решило продать некоторые из своих колод. Колоды принято выставлять на продажу в отсортированном по возратанию номеров карт виде. Однако колоды бывают такими большими, что ни один живой дилер не справится с их сортировкой.

Казино хочет узнать, способен ли робот-дилер отсортировать их колоду, и если да – то за сколько действий.

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

В первой строке записано одно число $n$ – количество карт в колоде у казино ($2 \le n \le 2 \cdot 10^5$, $n$ кратно $2$).

В следующей строке через пробел записано $n$ чисел $a_1, a_2, \dots, a_{n}$ ($1 \le a_i \le n$) – карты в том порядке, в котором они расположены в колоде, которую казино хочет продать. Номера всех карт попарно различны.

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

Если робот сможет отсортировать колоду казино, выведите минимально возможное число действий, через которое он это сделает. Если не сможет – выведите -1.

Подзадачи