题目描述

某实验室里生活着 $N=2^K$ 只老鼠。每只老鼠住在一个单独的笼子里，笼子从左到右编号为 $1$ 到 $N$。与笼子一一对应的，是另一排从左到右编号为 $1$ 到 $N$ 的食槽。

对于每只老鼠，都指定了它进食所使用的食槽编号，而且每个食槽恰好对应一只老鼠。每当铃声响起，所有老鼠都会沿着笼子与食槽之间的小路前往自己的食槽。显然，有些老鼠的路径会彼此相交，从而在小路上造成冲突。

实验室想重新安排老鼠所在的笼子位置，使得老鼠从笼子前往食槽时，路径交叉的总数尽可能少。

偏偏实验室主任刚刚学会二叉树，于是下达了下面的命令：

把这些笼子看成一棵高度为 $K$ 的满二叉树的叶子（提醒：$N=2^K$）。老鼠的调整必须成组进行：可以交换某个结点的两个子树对应叶子中的两组老鼠。组内老鼠的相对顺序不能改变。

换句话说，你可以对这棵满二叉树的任意结点执行一次“左右子树交换”操作；每次交换只会整体交换两个子树对应区间内的老鼠，而不会打乱各自区间内部顺序。

原题面中给出了一个示意例子，展示：

图片说明 1： 需要插入原题第一页中的示意图，表示初始时老鼠、食槽以及满二叉树结构。
图片说明 2： 需要插入原题第二页中的示意图，表示交换某个结点的左右子树后，路径交叉数反而增加的情形。
图片说明 3： 需要插入原题最后给出的最优交换结果示意图。

请编写程序 mice，给定老鼠最初对应的食槽排列，求通过上述允许的交换操作后，路径交叉数能够达到的最小值。

输入格式

第一行输入一个正整数 $K$。老鼠、笼子和食槽的总数为 $N=2^K$。

第二行输入 $N$ 个互不相同的整数 $a_1,a_2,\ldots,a_N$（即 $1$ 到 $N$ 的一个排列），其中：

• 第一个数表示最初住在笼子 $1$ 的老鼠所对应的食槽编号；
• 第二个数表示最初住在笼子 $2$ 的老鼠所对应的食槽编号；
• 以此类推。

输出格式

输出一行，一个整数，表示在允许进行若干次上述交换操作之后，老鼠路径交叉数的最小可能值。

数据范围

原题给出的限制为：

• $1 \le K \le 19$

等价地，$N=2^K$，因此 $N \le 524288$。

样例

输入

3
3 2 1 8 5 4 7 6

输出

6

样例解释

初始状态下（见题面第一幅图）共有 $9$ 条路径交叉。

为了达到最小交叉数，需要交换以下叶子对应的子树：

• $(1)$ 与 $(2)$
• $(5)$ 与 $(6)$
• $(7)$ 与 $(8)$

这里每个“子树”实际上都只包含一个叶子。完成这些交换后，最小交叉数为 $6$。

说明

两只老鼠的路径发生交叉，当且仅当它们在笼子中的先后顺序与它们对应食槽编号的先后顺序相反。