問題文

大きさ $N$ の順列 ($(1,~2,~...,~N)$ を並び替えてできる数列) $P,~Q$ があります。

大きさ $N$ の順列は $N!$ 通り考えられます。このうち、$P$ が辞書順で $a$ 番目に小さく、$Q$ が辞書順で $b$ 番目に小さいとして、$|a - b|$ を求めてください。

注記

$2$ つの数列 $X,~Y$ について、ある整数 $k$ が存在して $X_i = Y_i~(1 \\leq i < k)$ かつ $X_k < Y_k$ が成り立つとき、$X$ は $Y$ より辞書順で小さいと定義されます。

制約

• $2 \\leq N \\leq 8$
• $P,~Q$ は大きさ $N$ の順列である。
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $P_1$ $P_2$ $...$ $P_N$ $Q_1$ $Q_2$ $...$ $Q_N$

出力

$|a - b|$ を出力せよ。

入力例 1

3
1 3 2
3 1 2

出力例 1

3

大きさ $3$ の順列は、$(1,~2,~3)$、$(1,~3,~2)$、$(2,~1,~3)$、$(2,~3,~1)$、$(3,~1,~2)$、$(3,~2,~1)$ の $6$ 個あります。このうち $(1,~3,~2)$ は辞書順で $2$ 番目、$(3,~1,~2)$ は辞書順で $5$ 番目なので、答えは $|2 - 5| = 3$ です。

入力例 2

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

出力例 2

17517

入力例 3

3
1 2 3
1 2 3

出力例 3

0