Задача Bitris
Есть комплект из 2N кубиков. На каждом кубике написано одно натуральное число от 1 до N. Каждое из чисел написано ровно на двух кубиках. Кубики выставлены в одну колонку. Если два кубика с одинаковыми числами оказываются рядом, то они аннигилируют: оба кубики исчезают, а кубики, стоящие за ними, опускаются на освободившееся место. Нужно разобрать столбик - уничтожить все кубики. Для этого разрешается переставлять местами любые два рядом расположенных кубика. Перестановку можно делать только тогда, когда закончатся все возможные в данной ситуации аннигиляции.
Например, если N = 4, а кубики сначала стоят так:
|
2 |
|
4 |
|
1 |
|
3 |
|
3 |
|
4 |
|
1 |
|
2 |
то необходимо выполнить одну перестановку. Кубики с меткой 3 аннигилируют сразу;
|
2 |
|
4 |
|
1 |
|
4 |
|
1 |
|
2 |
переставим место четвертый снизу кубик (с меткой 1) и пятый снизу кубик (с меткой 4);
|
2 |
|
1 |
|
4 |
|
4 |
|
1 |
|
2 |
после этого аннигилируют последовательно кубики с меткой 4, с меткой 1 и с меткой 2. Можно, конечно, переставить третий и четвертый снизу кубики (в этом случае кубики с меткой 1 и с метка 4 аннигилируют одновременно, а вслед за ними аннигилируют кубики с меткой 2), можно второй и третий. Задача заключается в том, чтобы уничтожить все кубики , выполнив минимальное количество перестановок. Точнее - найти наименьшее необходимое для этого количество перестановок.
Технические условия. Программа Bitris читает с клавиатуры натуральное число N (2 ≤ N ≤ 100000), а дальше 2N чисел - метки кубиков от нижнего до верхнего. Все числа разделены одним пробелом. Программа выводит на экран одно целое неотрицательное число 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 |