eolymp
Змагання

Дерево Фенвика

Битрис

Имеется множество 2 × n кубов. Каждому кубу присвоено одно число от 1 до n, это число расположено на всех его сторонах. Каждое число записано в точности на двух кубах. Кубы расположены друг на друге, в одну стопку. Если два куба с одинаковым числом расположены рядом, то они аннигилируют: оба куба исчезают, а выше стоящие кубы опускаются на освободившееся место.

Ваша задача - разобрать кучу, уничтожить все кубики. Вам разрешается менять местами два соседних кубика. Перестановку можно выполнять только после совершения всех возможных аннигиляций.

prb3842.gif

Например, если n = 4, а кубики расположены как показано слева, то достаточно совершить один обмен. Кубики с номерами 3 аннигилируют сразу же; Вы меняете местами четвертый снизу куб (с номером 1) с пятым снизу кубом (с номером 4); далее кубики с номерами 4 аннигилируют, за которыми исчезают кубики с номерами 1 и 2. Другой вариант решения задачи - поменять местами третий и четвертый кубики снизу (в этом случае одновременно аннигилируют кубики с номерами 1 и 4, далее исчезают кубики с номерами 2). Можно также поменять второй и третий кубики местами.

Если n = 3, а кубики расположены как показано справа, то необходимо совершить 3 перестановки. Одно из решений - поменять местами пятый и шестой кубики, затем четвертый и пятый; кубики с номерами 2 аннигилируют; затем поменять местами второй и третий; оставшиеся кубики исчезнут одновременно.

Вам необходимо найти наименьшее количество обменов, в результате выполнения которых исчезнут все кубики.

Входные данные

Первая строка содержит натуральное число n (2n100000). Вторая строка содержит числа, записанные на кубах, в порядке снизу вверх.

Выходные данные

Вывести наименьшее количество обменов, достаточное для уничтожения всех кубиков.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4
2 1 4 3 3 1 4 2
Вихідні дані #1
1
Вхідні дані #2
3
1 3 2 1 3 2
Вихідні дані #2
3
Вхідні дані #3
3
1 3 2 2 3 1
Вихідні дані #3
0
Джерело 2012 Southeastern Europe Regional Contest, Бухарест, Винница, Октябрь 13, Задача B