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