C - 计数序列

分数：$300$ 分

问题描述

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

大小为 $N$ 的排列共有 $N!$ 种可能。在这些排列中，$P$ 和 $Q$ 分别是字典序第 $a$ 个和第 $b$ 个最小的排列。求 $|a - b|$。

注意

对于两个序列 $X$ 和 $Y$，当且仅当存在整数 $k$ 使得对于 $1 \leq i < k$，$X_i = Y_i$ 且 $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|$。

3
1 3 2
3 1 2

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

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