問題文

$N$ 頂点からなる木と $N$ 種類の置物があります。
木の頂点には $1$ から $N$ まで番号が付いており，$i=2,3,4,...,N$ について，$i$ の親は $\lfloor \frac{i}{2} \rfloor$ です。$\lfloor x \rfloor$ とは，$x$ の小数点以下を切り捨てた整数値です。
置物にも $1$ から $N$ まで番号が付いており，$j=1,2,...,N$ について，置物 $j$ は頂点 $A_j$ に置かれています。このとき，各頂点にはただ $1$ つの置物が置かれていることが保証されています。
Ajinoko君は木と置物に対して次の操作を $0$ 回以上行うことができます。

• 頂点 $1$ 以外の頂点を $1$ つ選ぶ。選んだ頂点を $v$ とすると，頂点 $v$ に置かれている置物と，頂点 $v$ の親に置かれている置物を入れ替える。

Ajinoko君が次の目標を達成するまでに必要な操作回数の最小値を求めてください。

• 各頂点にはただ $1$ つの置物が置かれており，$j=1,2,...,N$ について，置物 $j$ は頂点 $B_j$ に置かれている。

なお，適当に操作を行うと目標を達成できることは証明できます。

制約

• $2 \leq N \leq 8$
• $1 \leq A_i \leq N$
• $1 \leq B_j \leq N$
• $i \neq i' \Rightarrow A_i \neq A_{i'}$
• $j \neq j' \Rightarrow B_j \neq B_{j'}$
• 入力はすべて整数

入力

出力

目標を達成するまでに必要な操作回数の最小値を出力してください。

サンプル1

4
1 2 3 4
4 3 1 2

3

はじめは置物 $1$ は頂点 $1$ ，置物 $2$ は頂点 $2$ ，置物 $3$ は頂点 $3$ ，置物 $4$ は頂点 $4$ にあります。
以下の順で操作を行うことで目標を達成できます。

• 頂点 $4$ を選ぶ。頂点 $4$ にある置物 $4$ と，その親頂点 $2$ にある置物 $2$ を入れ替える。
• 頂点 $3$ を選ぶ。頂点 $3$ にある置物 $3$ と，その親頂点 $1$ にある置物 $1$ を入れ替える。
• 頂点 $2$ を選ぶ。頂点 $2$ にある置物 $4$ と，その親頂点 $1$ にある置物 $3$ を入れ替える。

上記の操作回数は $3$ 回であり，これより少ない操作回数で目標を達成することはできません。

サンプル2

5
2 3 5 1 4
2 3 5 1 4

0

はじめから目標を達成しています。

サンプル3

7
4 2 6 3 5 1 7
6 7 5 2 4 3 1

11