令 $x_0, \dots, x_{n-1}$ 表示 $n$ 个布尔变量（即只能取值 $0$ 和 $1$ 的变量）。这些变量上的二元决策图（Binary Decision Diagram，简称 BDD）是输入为 $f(x_0, \dots, x_{n-1})$ 的布尔函数的图形化表示。

BDD 是一棵有根二叉树，满足所有内部节点 $v$ 都恰好有两个子节点。连接内部节点 $v$ 及其子节点的边分别标记为 $0$ 或 $1$（每种标记恰好一个）。每个叶子节点也标记为 $0$ 或 $1$。我们注意到，BDD 可以仅由单个节点组成，该节点既是根节点又是叶子节点。

给定输入 $(x_0, \dots, x_{n-1})$，由 BDD 表示的布尔函数的求值过程如下：

• 令 $v$ 为根节点
• 令 $i \leftarrow 0$
• 当 $v$ 不是叶子节点时，执行：
  • 沿着标记为 $x_i$ 的边移动，将 $v$ 替换为 $v$ 的子节点
  • 将 $i$ 增加 $1$
• 输出叶子节点 $v$ 的标记

考虑上图 BDD 所表示的函数 $f(x_0, x_1, x_2)$。为了计算 $f(1, 0, 1)$，我们从根节点开始，沿着标记为 $1$、$0$、然后是 $1$ 的边向下移动。我们到达了一个标记为 $1$ 的叶子节点，因此 $f(1, 0, 1) = 1$。

如果无法通过将 BDD 的任何内部节点的子树替换为单个叶子节点来获得定义相同布尔函数的新 BDD，则称该 BDD 是极小的（minimal）。上图所示的 BDD 就是极小的。事实上，对于每个布尔函数 $f$，都存在唯一一个表示该布尔函数的极小 BDD。

在本题中，给定一个 $n$ 变量布尔函数，由该函数在各种输入下应取值的 $2^n$ 个不同值的列表指定。计算表示该函数的极小 BDD 中的节点数。

输入格式

输入的第一行包含一个整数 $1 \le n \le 18$。

接下来的一行包含 $2^n$ 个值（$0$ 或 $1$），描述一个 $n$ 变量布尔函数。

我们认为这些值的索引从 $0$ 到 $2^n - 1$。第 $i$ 个值表示 $f(x_0, \dots, x_{n-1})$，其中 $x_j$ 是 $i$ 的二进制表示中第 $j$ 个最低有效位（least-significant bit）。换句话说，$x_j$ 是 $i$ 的二进制展开式中 $2^j$ 的系数。

下方的第三个样例输入对应于上图所示的 BDD。

输出格式

输出包含一个整数 $m$，表示表示输入布尔函数的唯一极小 BDD 中的节点数。

样例

输入样例 1

2
1 1 0 1

输出样例 1

5

输入样例 2

2
0 0 0 0

输出样例 2

1

输入样例 3

3
1 0 1 0 1 1 1 0

输出样例 3

7