Problems
Tanglegram (RU)
Tanglegram (RU)
\includegraphics{https://static.e-olymp.com/content/ee/ee2889597160fc1ca5bfe8a0a4d2d4f4499a78e5.jpg}
На плоскости расположены два полных бинарных дерева глубины \textbf{N}. Их \textbf{2x2^N} листьев расположены на двух параллельных прямых и пронумерованы слева направо. Листья с одинаковыми номерами в первом и втором деревьях находятся один напротив другого. Между листьями деревьев задано соответствие -- каждый из листьев одного дерева имеет ровно один соответствующий ему лист во втором дереве, и наоборот. На рисунке такие соответствия заданы прямыми отрезками между листьями. Такую конструкцию -- два дерева вместе с соответствиями между листьями -- называют танглеграмом. Танглеграмы, например, используются биологами при исследовании взаимосвязей генов разных видов растений.
Танглеграм тяжело исследовать, если многие из отрезков-соответствий пересекаются. Для того, чтобы уменьшить количество пересечений, разрешается осуществлять единственную операцию: в первом (верхнем) дереве можно менять местами два поддерева произвольной вершины, как изображено на втором рисунке.
\textbf{Задание}
Напишите программу, которая по информации о соответствии между листьями двух деревьев определит наименьшее возможное количество пересечений отрезков в графическом представлении танглеграма, которое может быть достигнуто путем выполнения операций обмена смежных поддеревьев первого дерева. Если в одной точке пересекаются больше двух отрезков, то под количеством пересечений нужно понимать количество попарных пересечений отрезков. Например, на первом рисунке соответствия \textbf{4}-\textbf{8}, \textbf{5}-\textbf{5} и \textbf{6}-\textbf{4} образуют три пересечения.
\InputFile
В первой строке находится натуральное число \textbf{N }(\textbf{1 ≤ N ≤ 19}) - глубина деревьев. Вторая строка содержит \textbf{2^N} разных целых чисел от \textbf{1 }до \textbf{2^N}, каждое \textbf{i}-ое из которых задает лист второго дерева, который связан отрезком с \textbf{i}-ым листом первого дерева.
\OutputFile
Вывести наименьшее возможное количество пересечений отрезков-соответствий в танглеграме, которое может быть достигнуто путем обмена поддеревьев в первом дереве.
Input example #1
3 3 2 1 8 5 4 7 6
Output example #1
6