分数: 300 点
问题陈述
我们有两种排列 P 和 Q 尺寸 N (即 P 和 Q 都是重新排列 (1,~2,~...,~N)).
有 N! 可能的大小排列 N。其中,让 P 和 Q 是 a-th 和 b- 按字典顺序排列的最小排列。查找 |a - b|.
注释
对于两个序列 X 和 Y, X 据说按字典顺序小于 Y 当且仅当存在一个整数 k 这样 X_i = Y_i~(1 \leq i < k) 和 X_k < Y_k.
约束
- 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
有 6 大小排列 3: (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- 按字典顺序排列,所以答案是 |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