Танглеграм
На плоскости расположены два полных бинарных дерева глубины N. Их 2x2^(N) листьев расположены на двух параллельных прямых и пронумерованы слева направо. Листья с одинаковыми номерами в первом и втором деревьях находятся один напротив другого. Между листьями деревьев задано соответствие - каждый из листьев одного дерева имеет ровно один соответствующий ему лист во втором дереве, и наоборот. На рисунке такие соответствия заданы прямыми отрезками между листьями. Такую конструкцию - два дерева вместе с соответствиями между листьями - называют танглеграмом. Танглеграмы, например, используются биологами при исследовании взаимосвязей генов разных видов растений.
Танглеграм тяжело исследовать, если многие из отрезков-соответствий пересекаются. Для того, чтобы уменьшить количество пересечений, разрешается осуществлять единственную операцию: в первом (верхнем) дереве можно менять местами два поддерева произвольной вершины, как изображено на втором рисунке.
Задание
Напишите программу, которая по информации о соответствии между листьями двух деревьев определит наименьшее возможное количество пересечений отрезков в графическом представлении танглеграма, которое может быть достигнуто путем выполнения операций обмена смежных поддеревьев первого дерева. Если в одной точке пересекаются больше двух отрезков, то под количеством пересечений нужно понимать количество попарных пересечений отрезков. Например, на первом рисунке соответствия 4-8, 5-5 и 6-4 образуют три пересечения.
Входные данные
В первой строке находится натуральное число N (1 ≤ N ≤ 19) - глубина деревьев. Вторая строка содержит 2^(N) разных целых чисел от 1 до 2^(N), каждое i-ое из которых задает лист второго дерева, который связан отрезком с i-ым листом первого дерева.
Выходные данные
Вывести наименьшее возможное количество пересечений отрезков-соответствий в танглеграме, которое может быть достигнуто путем обмена поддеревьев в первом дереве.