题目描述

我们有两个长度为 $N$ 的排列 $P$ 和 $Q$（即 $P$ 和 $Q$ 都是 $(1,~2,~...,~N)$ 的重新排列）。

在大小为 $N$ 的排列中，有 $N!$ 种可能的排列方式。在这些排列中，设 $P$ 是字典序第 $a$ 小的排列，$Q$ 是字典序第 $b$ 小的排列，求 $|a - b|$。

注意事项

对于两个序列 $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$ 的排列中，共有 $6$ 种排列方式：$(1,~2,~3)$, $(1,~3,~2)$, $(2,~1,~3)$, $(2,~3,~1)$, $(3,~1,~2)$ 和 $(3,~2,~1)$。其中，$(1,~3,~2)$ 和 $(3,~1,~2)$ 分别是字典序第 $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