eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Танглеграм

Танглеграм

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
prb222

На плоскости расположены два полных бинарных дерева глубины N. Их 2x2^(N) листьев расположены на двух параллельных прямых и пронумерованы слева направо. Листья с одинаковыми номерами в первом и втором деревьях находятся один напротив другого. Между листьями деревьев задано соответствие - каждый из листьев одного дерева имеет ровно один соответствующий ему лист во втором дереве, и наоборот. На рисунке такие соответствия заданы прямыми отрезками между листьями. Такую конструкцию - два дерева вместе с соответствиями между листьями - называют танглеграмом. Танглеграмы, например, используются биологами при исследовании взаимосвязей генов разных видов растений.

Танглеграм тяжело исследовать, если многие из отрезков-соответствий пересекаются. Для того, чтобы уменьшить количество пересечений, разрешается осуществлять единственную операцию: в первом (верхнем) дереве можно менять местами два поддерева произвольной вершины, как изображено на втором рисунке.

Задание

Напишите программу, которая по информации о соответствии между листьями двух деревьев определит наименьшее возможное количество пересечений отрезков в графическом представлении танглеграма, которое может быть достигнуто путем выполнения операций обмена смежных поддеревьев первого дерева. Если в одной точке пересекаются больше двух отрезков, то под количеством пересечений нужно понимать количество попарных пересечений отрезков. Например, на первом рисунке соответствия 4-8, 5-5 и 6-4 образуют три пересечения.

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

В первой строке находится натуральное число N (1 ≤ N ≤ 19) - глубина деревьев. Вторая строка содержит 2^(N) разных целых чисел от 1 до 2^(N), каждое i-ое из которых задает лист второго дерева, который связан отрезком с i-ым листом первого дерева.

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

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

Пример

Входные данные #1
3
3 2 1 8 5 4 7 6
Выходные данные #1
6
Автор Тарас Галковский
Источник 2009 XXII Всеукраинская олимпиада по информатике, Хмельницкий, Март 22 - 27, тур 1