Школьники Алиса и Ибрагим — лучшие друзья. У Ибрагима скоро день рождения, и по этому поводу Алиса решила подарить ему новый пазл. Пазл можно представить в виде матрицы из \(2\) строк и \(n\) столбцов, каждый элемент которой — \(0\), либо \(1\). За один ход можно поменять местами два элемента, стоящие в соседних клетках.
Более формально, будем считать, что строки матриц пронумерованы сверху вниз от \(1\) до \(2\), а столбцы — слева направо от \(1\) до \(n\). Обозначим клетку на пересечении строки \(x\) и столбца \(y\) за \((x, y)\). Будем считать две клетки \((x_1, y_1)\) и \((x_2, y_2)\) соседними, если \(|x_1 - x_2| + |y_1 - y_2| = 1\).
Алисе не нравится, какой рисунок образуют клетки пазла в данный момент. Она придумала свой рисунок, с которым и планирует подарить Ибрагиму новый пазл. Помогите Алисе найти минимальное количество ходов, за которое она может получить свой рисунок, или скажите, что это невозможно.
Примечание
В первом примере из условия подойдет следующая последовательность обменов:
- \((2, 1), (1, 1)\),
- \((1, 2), (1, 3)\),
- \((2, 2), (2, 3)\),
- \((1, 4), (1, 5)\),
- \((2, 5), (2, 4)\).
Можно показать, что меньшим числом обменов обойтись нельзя, поэтому ответ равен \(5\).
Во втором примере из условия никакая последовательность ходов не приводит пазл к нужному виду. Следовательно, ответ \(-1\).