Problem G
Decisions, Decisions
Let $x_0, \ldots , x_{n1}$ 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_{n1})$ 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_{n1})$, 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^ n1$. The $i$th such value represents $f(x_0, \ldots , x_{n1})$ where $x_ j$ is the $j$th leastsignificant 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.
Sample Input 1  Sample Output 1 

2 1 1 0 1 
5 
Sample Input 2  Sample Output 2 

2 0 0 0 0 
1 
Sample Input 3  Sample Output 3 

3 1 0 1 0 1 1 1 0 
7 