Decisions, Decisions

Let $x_0, \dots, x_{n-1}$ be $n$ boolean variables, that is, variables taking only the values 0 and 1. A binary decision diagram (BDD) over these variables is a diagrammatic representation of a boolean function $f(x_0, \dots, x_{n-1})$.

A BDD is a rooted binary tree in which every internal vertex has exactly two children. The two edges joining an internal vertex $v$ to its children are labelled 0 and 1, one each. Every leaf vertex is labelled 0 or 1. A BDD may consist of a single vertex, and that vertex is then both the root and a leaf.

Given an input $(x_0, \dots, 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 of $v$ reached by the edge labelled $x_i$
  • increase $i$ by 1
• output the label of the leaf vertex $v$

Consider the function $f(x_0, x_1, x_2)$ represented by the BDD in the picture. To evaluate $f(1, 0, 1)$ you start at the root and descend along the edges labelled 1, 0, and then 1. You reach a leaf labelled 1, so $f(1, 0, 1) = 1$.

A BDD is minimal if there is no way to replace the subtree of an internal vertex by a single leaf and obtain a BDD defining the same boolean function. The BDD in the picture is minimal. For every boolean function the minimal BDD representing it is unique.

In this problem an $n$-variable boolean function is given as the list of the $2^n$ values it takes. Compute the number of vertices of the minimal BDD representing this function.

The first line contains one integer $n$ ($1 \le n \le 18$). The second line contains $2^n$ values describing an $n$-variable boolean function. Each value is 0 or 1.

The values are indexed from 0 to $2^n - 1$. The $i$-th value is $f(x_0, \dots, x_{n-1})$, where $x_j$ is the coefficient of $2^j$ in the binary expansion of $i$, that is, the $j$-th least significant bit of $i$.

The third sample input corresponds to the BDD in the picture.

Print one integer $m$, the number of vertices of the unique minimal BDD representing the boolean function from the input.