Бітріс

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

Наприклад, якщо $N$ = $4$, а кубики спочатку стоять так:

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

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

після цього анігілюють послідовно кубики з міткою $4$, з міткою $1$ і з міткою $2$. Можна, звичайно, переставити третій і четвертий знизу кубики (в цьому випадку кубики з міткою $1$ і з міткою $4$ анігілюють одночасно, а вслід за ними анігілюють кубики з міткою $2$), можна другий і третій. Задача полягає в тому, щоб знищити усі кубики, виконавши найменш можливу кількість перестановок. Точніше, знайти найменшу необхідну для цього кількість перестановок.

Вхідні дані

Програма Bitris читає з клавіатури натуральне число $N$ ($2$ ≤ $N$ ≤ $100000$), а далі $2\ast N$ чисел − мітки кубиків від нижнього до верхнього. Всі числа розділені одним пробілом.

Вихідні дані

Програма виводить на екран одне ціле невід’ємне число $M$ – найменшу кількість перестановок, необхідну для знищення усього стовпчика.

Приклади