Problem H. Сортировка
Input file name: sorting.in
Output file name: sorting.out
Time limit: 2 s
Memory limit: 256 MB

Не так давно Рома стал свидетелем того, как шеф-повар в ресторане лихо переворачивал сразу по три рядом лежащие отбивные на гриле при помощи специальной лопатки. Это натолкнуло Рому на мысль о новом методе сортировки массивов, где за один шаг выполняется разворот некоторой тройки подряд идущих элементов.

Задан массив размера N. Доступна такая операция: заменить три последовательных элемента массива (x, y, z) на эти же элементы, но в обратном порядке (z, y, x). Помогите Роме определить, можно ли упорядочить массив по возрастанию и какое минимальное число операций для этого необходимо.

Input

В первой строке записано целое число N (1 ≤ N ≤ 1 000 000). Во второй строке через пробел записаны элементы массива — попарно различные целые числа от 1 до N.

Output

Выведите одно число — минимальное количество операций, или −1, если отсортировать массив указанным способом нельзя.

Examples


sorting.in sorting.out
6
3 4 1 6 5 2
3
5
3 1 5 4 2
-1

Note

В первом примере одна из возможных последовательностей операций такова: