Tanglegram#222
On a plane, there are two complete binary trees, each of depth . Their 2^N leaves are arranged along two parallel lines and numbered from left to right. Leaves with the same number in the two trees are directly opposite each other.
A one-to-one correspondence is established between the leaves of the trees—each leaf in one tree is paired with exactly one leaf in the other tree. In the illustration, these correspondences are depicted as straight segments joining the leaves. Such a construction—two trees together with the correspondence between their leaves—is called a tanglegram. Tanglegrams are used, for example, by biologists to study the relationships between genes of different plant species.
When many of the correspondence segments intersect, a tanglegram becomes difficult to analyze. To decrease the number of intersections, you are allowed one operation: in the first (upper) tree, you may swap the two subtrees of any vertex, as shown in the second illustration.
Task
Given the information about the leaf correspondence of the two trees, write a program to calculate the minimum number of intersection points between the segments in the tanglegram's graphical representation that can be achieved by performing subtree swaps in the first tree. If more than two segments intersect at the same point, count the number of pairwise intersections among them. For example, in the first illustration, the correspondences , , and produce three intersections.
The first line contains a natural number (1 \leq N \leq 19), the depth of the trees. The second line contains 2^N distinct integers from to 2^N. Each -th of these specifies the leaf of the second tree joined by a segment to the -th leaf of the first tree.
Print the minimum possible number of intersections of the correspondence segments in the tanglegram that can be achieved by subtree swaps in the first tree.
Example 1