← 返回题目列表

AtCoder · abc150_c

C. 计数顺序

中文机器翻译题面 查看原题

分数: 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