결정, 또 결정

$x_0, \dots, x_{n-1}$을 $n$개의 불 변수라고 하자. 불 변수는 0과 1만 값으로 취한다. 이 변수들 위의 이진 결정 다이어그램(BDD)은 불 함수 $f(x_0, \dots, x_{n-1})$을 그림으로 나타낸 것이다.

BDD는 모든 내부 정점이 자식을 정확히 두 개 갖는 뿌리 있는 이진 트리다. 내부 정점 $v$와 두 자식을 잇는 간선에는 0과 1이 하나씩 적혀 있다. 잎 정점에도 0 또는 1이 적혀 있다. BDD가 정점 하나로만 이루어질 수도 있고, 이때 그 정점은 뿌리이면서 잎이다.

입력 $(x_0, \dots, x_{n-1})$이 주어지면 BDD가 나타내는 불 함수를 다음과 같이 계산한다.

• $v$를 뿌리 정점으로 둔다
• $i \leftarrow 0$으로 둔다
• $v$가 잎이 아닌 동안 다음을 반복한다
  • $x_i$가 적힌 간선을 따라가서 $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라고 한다. 그림의 BDD는 최소다. 불 함수마다 그것을 나타내는 최소 BDD는 유일하다.

이 문제에서는 $n$변수 불 함수를 그 함수가 취하는 $2^n$개의 값으로 준다. 이 함수를 나타내는 최소 BDD의 정점 개수를 구하여라.

첫째 줄에 정수 $n$ ($1 \le n \le 18$)이 주어진다. 둘째 줄에 $n$변수 불 함수를 나타내는 $2^n$개의 값이 주어진다. 각 값은 0 또는 1이다.

이 값들에는 0부터 $2^n - 1$까지 번호가 붙어 있다. $i$번째 값이 $f(x_0, \dots, x_{n-1})$이고, $x_j$는 $i$를 이진법으로 나타냈을 때 $2^j$의 계수, 즉 $i$의 아래에서 $j$번째 비트다.

세 번째 예제 입력이 그림의 BDD에 해당한다.

입력으로 주어진 불 함수를 나타내는 유일한 최소 BDD의 정점 개수 $m$을 한 줄에 출력한다.