字典序排名

题目描述

有大小为 $N$ 的排列(将 $(1,~2,~...,~N)$ 重新排列得到的数列)$P,~Q$。

大小为 $N$ 的排列共有 $N!$ 种。设 $P$ 在所有排列中按字典序从小到大排第 $a$ 个,$Q$ 排第 $b$ 个,求 $|a - b|$。

输入格式

输入按以下格式从标准输入给出:

$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,~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$。

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

数据范围

• $2 \leq N \leq 8$
• $P,~Q$ 是大小为 $N$ 的排列。
• 输入均为整数。

提示

对于两个数列 $X,~Y$,如果存在某个整数 $k$,使得 $X_i = Y_i~(1 \leq i \lt k)$ 且 $X_k \lt Y_k$,则定义 $X$ 按字典序小于 $Y$。