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