配点 : $300$ 点

問題文

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

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

注記

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

制約

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

入力

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

$N$

$P_1$ $P_2$ $...$ $P_N$

$Q_1$ $Q_2$ $...$ $Q_N$

出力

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

3
1 3 2
3 1 2

3

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

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

17517

3
1 2 3
1 2 3

0