Задача Bitris

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

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

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

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