Аллен собрал вечеринку в формальном стиле. Пришло \(2n\) человек, образующих \(n\) пар. После веселья Аллен хочет выстроить всех в ряд, чтобы сделать общую фотографию. \(2n\) гостей встали в ряд, но Аллену не нравится порядок. Аллен хочет, чтобы каждая пара располагалась рядом, это сделает фотографию более эстетичной.
Определите для Аллена минимальное число обмена мест людей на соседних позициях, необходимое для того, чтобы каждая пара занимала соседние места в ряду.
Выходные данные
Выведите одно целое число — минимальное число обменов местами соседних людей для того, чтобы каждая пара занимала соседние позиции.
Примечание
В первом примере можно добиться результата следующим образом: \(1 1 2 3 3 2 4 4 \rightarrow 1 1 2 3 2 3 4 4 \rightarrow 1 1 2 2 3 3 4 4\) за два шага. Обратите внимание, что последовательность \(1 1 2 3 3 2 4 4 \rightarrow 1 1 3 2 3 2 4 4 \rightarrow 1 1 3 3 2 2 4 4\) тоже подходит.
Во втором примере все пары уже стоят рядом, поэтому ответ \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1 2 3 3 2 4 4
|
2
|
|
2
|
3
1 1 2 2 3 3
|
0
|
|
3
|
3
3 1 2 3 1 2
|
3
|