Бітріс
Бітріс
Є комплект із $2*N$ кубиків. На кожному кубику написано одне натуральне число від $1$ до $N$. Кожне із чисел написано рівно на двох кубиках. Кубики виставлені в одну колонку. Якщо два кубика з однаковими числами опиняються поруч, то вони анігілюють: обидва кубики зникають, а кубики, які стоять над ними, опускаються на звільнене місце. Потрібно розібрати стовпчик – знищити усі кубики. Для цього дозволяється переставляти місцями будь-які два поруч розташованих кубика. Перестановку можна робити тільки тоді, коли закінчаться всі можливі в даній ситуації анігіляції.
Наприклад, якщо $N$ = $4$, а кубики спочатку стоять так:
то необхідно виконати одну перестановку. Кубики з міткою $3$ анігілюють одразу;
переставимо місцями четвертий знизу кубик (з міткою $1$) і п’ятий знизу кубик (з міткою $4$);
після цього анігілюють послідовно кубики з міткою $4$, з міткою $1$ і з міткою $2$. Можна, звичайно, переставити третій і четвертий знизу кубики (в цьому випадку кубики з міткою $1$ і з міткою $4$ анігілюють одночасно, а вслід за ними анігілюють кубики з міткою $2$), можна другий і третій. Задача полягає в тому, щоб знищити усі кубики, виконавши найменш можливу кількість перестановок. Точніше, знайти найменшу необхідну для цього кількість перестановок.
Вхідні дані
Програма Bitris читає з клавіатури натуральне число $N$ ($2$ ≤ $N$ ≤ $100000$), а далі $2*N$ чисел − мітки кубиків від нижнього до верхнього. Всі числа розділені одним пробілом.
Вихідні дані
Програма виводить на екран одне ціле невід’ємне число $M$ – найменшу кількість перестановок, необхідну для знищення усього стовпчика.
4 2 1 4 3 3 1 4 2
1
3 1 3 2 1 3 2
3
3 1 3 2 2 3 1
0