Задача Bitris

Є комплект із 2N кубиків. На кожному кубику написано одне натуральне число від1 до N. Кожне із чисел написано рівно на двох кубиках. Кубики виставлені в одну колонку. Якщо два кубика з однаковими числами опиняються поруч, то вони анігілюють: обидва кубики зникають, а кубики, які стоять над ними, опускаються на звільнене місце. Потрібно розібрати стовпчик – знищити усі кубики. Для цього дозволяється переставляти місцями будь-які два поруч розташованих кубика. Перестановку можна робити тільки тоді, коли закінчаться всі можливі в даній ситуації анігіляції.
Наприклад, якщо N=4, а кубики спочатку стоять так:

то необхідно виконати одну перестановку. Кубики з міткою 3 анігілюють одразу;

 переставимо місцями четвертий знизу кубик (з міткою 1) і п’ятий знизу кубик (з міткою 4);                           

після цього анігілюють послідовно кубики з міткою 4, з міткою 1 і з міткою 2. Можна, звичайно, переставити третій і четвертий знизу кубики (в цьому випадку кубики з міткою 1 і з міткою 4 анігілюють одночасно, а вслід за ними анігілюють кубики з міткою 2), можна другий і третій.Задача полягає в тому, щоб знищити усі кубики, виконавши найменш  можливу кількість перестановок. Точніше, знайти найменшу необхідну для цього кількість перестановок.
Технічні умови. Програма Bitris читає з клавіатури натуральне число N(2≤N≤100000), а далі  2N  чисел - мітки кубиків від нижнього до верхнього. Всі числа розділені одним пробілом. Програма виводить на екран одне ціле невід’ємне число M – найменшу кількість перестановок, необхідну для знищення усього стовпчика.

Приклади: