Problem F
Decisions, Decisions

Let $x_0, \ldots , x_{n-1}$ denote $n$ boolean variables (i.e., variables taking only values $0$ and $1$). A binary decision diagram (BDD) over these variables is a diagrammatic representation of a boolean function $f(x_0, \ldots , x_{n-1})$ as inputs.

A BDD is a rooted binary tree such that all internal vertices $v$ have precisely two children. The edges connecting an internal vertex $v$ with its children are labelled with a $0$ or $1$ (exactly one of each). Each leaf vertex is also labelled with a $0$ or $1$. We note that a BDD may consist of a single vertex, which is considered to be both the root and a leaf vertex.

Given input $(x_0, \ldots , x_{n-1})$, the boolean function represented by the BDD is evaluated as follows.

• let $v$ be the root vertex

• let $i \leftarrow 0$

• while $v$ is not a leaf do

  • replace $v$ with the child vertex of $v$ by traversing the edge labelled $x_ i$

  • increase $i$ by $1$

• output the label of leaf vertex $v$

Consider the function $f(x_0,x_1,x_2)$ represented by the BDD above. To evaluate $f(1,0,1)$, we start from the root, we descend along edges labelled $1$, $0$, and then $1$. We reach a leaf vertex labelled $1$, so $f(1,0,1) = 1$.

A BDD is minimal if there is no way to replace any subtree of an internal vertex of the BDD by a single leaf vertex to get a new BDD defining the same boolean function. The BDD depicted above is minimal. It is a fact that for each boolean function $f$, there is a unique minimal BDD that represents the boolean function.

In this problem, you are given an $n$-variable boolean function specified by a list of the $2^ n$ different values the function should take for various inputs. Compute the number of vertices in the minimal BDD representing this function.

Input

The first line of input consists of a single integer $1 \leq n \leq 18$. Then one more line follows that contains $2^ n$ values (either $0$ or $1$) describing an $n$-variable boolean function.

We think of these values as being indexed from $0$ to $2^ n-1$. The $i$th such value represents $f(x_0, \ldots , x_{n-1})$ where $x_ j$ is the $j$th least-significant bit of the binary representation of $i$. In other words, $x_ j$ is the coefficient of $2^ j$ in the binary expansion of $i$.

The third sample input below corresponds to the BDD depicted above.

Output

Output consists of a single integer $m$ that is the number of vertices in the unique minimal BDD representing the boolean function from the input.

2
1 1 0 1

5

2
0 0 0 0

1

3
1 0 1 0 1 1 1 0

7