У вас есть шахматная доска размера 1 × n. Гарантируется, что n четно. Доска раскрашена следующим образом: «BWBW...BW».
В некоторых клетках доски расположены шахматные фигуры. В каждой клетке расположено не более одной фигуры. Также известно, что общее количество фигур на доске равняется 
.
За один ход вы можете передвинуть любую фигуру на одну клетку от ее текущей позиции влево или вправо. Запрещено передвигать фигуры за границы доски. Также запрещено передвигать фигуры в клетки, в которых уже есть другие фигуры.
Ваша задача — за минимальное количество ходов расставить фигуры таким образом, чтобы все они располагались в клетках одинакового цвета (то есть после всех сделанных ходов все фигуры должны быть расположены либо только в черных клетках, либо только в белых клетках).
Выходные данные
Выведите одно целое число — минимальное количество ходов, за которое вы можете расставить все фигуры в клетках одного цвета.
Примечание
В первом примере единственная возможная стратегия — передвинуть фигуру с позиции 6 на позицию 5 и передвинуть фигуру с позиции 2 на позицию 3. Заметьте, что если вы будете расставлять фигуры в клетки белого цвета, минимальное количество ходов будет равно 3.
Во втором примере возможна следующая стратегия: передвинуть 
за 4 хода, затем 
за 3 хода, 
за 2 хода и 
за 1 ход.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2 6
|
2
|
|
2
|
10
1 2 3 4 5
|
10
|