题目描述

We have two permutations $P$ and $Q$ of size $N$ (that is, $P$ and $Q$ are both rearrangements of $(1,~2,~...,~N)$).

There are $N!$ possible permutations of size $N$. Among them, let $P$ and $Q$ be the $a$-th and $b$-th lexicographically smallest permutations, respectively. Find $|a - b|$.

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

大小为 $N$ 的可能排列有 $N!$ 种。其中 $P$ 和 $Q$ 分别是 $a$ -th和 $b$ -th词典上最小的排列。求 $|a - b|$ 。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印 $|a - b|$ .

样例 #1

样例输入 #1

3
1 3 2
3 1 2

样例输出 #1

3

样例 #2

样例输入 #2

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

样例输出 #2

17517

样例 #3

样例输入 #3

3
1 2 3
1 2 3

样例输出 #3

0

说明

对于两个序列 $X$ 和 $Y$ 而言，当且仅当存在一个整数 $k$ 使得 $X_i = Y_i~(1 \leq i \lt k)$ 和 $X_k \lt Y_k$ 小于 $Y$ 时，才称 $X$ 在词序上小于 $Y$ 。

数据规模与约定

• $2 \leq N \leq 8$
• $P$ 和 $Q$ 是大小为 $N$ 的排列。

样例 $1$ 解释

大小为 $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$ （nd）和 $5$ （th），因此答案为 $|2 - 5| = 3$ 。