Битрис
Имеется множество 2 × n кубов. Каждому кубу присвоено одно число от 1 до n, это число расположено на всех его сторонах. Каждое число записано в точности на двух кубах. Кубы расположены друг на друге, в одну стопку. Если два куба с одинаковым числом расположены рядом, то они аннигилируют: оба куба исчезают, а выше стоящие кубы опускаются на освободившееся место.
Ваша задача - разобрать кучу, уничтожить все кубики. Вам разрешается менять местами два соседних кубика. Перестановку можно выполнять только после совершения всех возможных аннигиляций.
Например, если n = 4, а кубики расположены как показано слева, то достаточно совершить один обмен. Кубики с номерами 3 аннигилируют сразу же; Вы меняете местами четвертый снизу куб (с номером 1) с пятым снизу кубом (с номером 4); далее кубики с номерами 4 аннигилируют, за которыми исчезают кубики с номерами 1 и 2. Другой вариант решения задачи - поменять местами третий и четвертый кубики снизу (в этом случае одновременно аннигилируют кубики с номерами 1 и 4, далее исчезают кубики с номерами 2). Можно также поменять второй и третий кубики местами.
Если n = 3, а кубики расположены как показано справа, то необходимо совершить 3 перестановки. Одно из решений - поменять местами пятый и шестой кубики, затем четвертый и пятый; кубики с номерами 2 аннигилируют; затем поменять местами второй и третий; оставшиеся кубики исчезнут одновременно.
Вам необходимо найти наименьшее количество обменов, в результате выполнения которых исчезнут все кубики.
Входные данные
Первая строка содержит натуральное число n (2 ≤ n ≤ 10^5). Вторая строка содержит числа, записанные на кубах, в порядке снизу вверх.
Выходные данные
Вывести наименьшее количество обменов, достаточное для уничтожения всех кубиков.