题目描述

给定整数 $N$，以及两个 $(1, 2, \ldots, N)$ 的排列 $P = (P_1, P_2, \ldots, P_N)$ 和 $Q = (Q_1, Q_2, \ldots, Q_N)$。

请求出有多少个 $(1, 2, \ldots, N)$ 的排列，按字典序严格大于 $P$ 且严格小于 $Q$。

什么是字典序？

对两个整数序列 $S$ 和 $T$，称 $S$ 字典序小于 $T$，当且仅当下面两条之一成立：

1. $|S| < |T|$ 且 $S$ 是 $T$ 的前缀，即 $(S_1, \ldots, S_{|S|}) = (T_1, \ldots, T_{|S|})$；
2. 存在整数 $1 \le i \le \min(|S|, |T|)$，使得 $(S_1, \ldots, S_{i-1}) = (T_1, \ldots, T_{i-1})$ 且 $S_i < T_i$。

通俗地说，就是像查字典一样，从左往右逐位比较，第一个不同的位置谁小谁就小。

输入格式

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

输出格式

输出满足条件的排列个数。

输入示例 1

3
1 3 2
3 1 2

输出示例 1

2

示例 1 说明

$N = 3$ 的全部 $6$ 个排列按字典序排列为：

$$(1,2,3) < (1,3,2) < (2,1,3) < (2,3,1) < (3,1,2) < (3,2,1)$$

严格夹在 $P = (1,3,2)$ 与 $Q = (3,1,2)$ 之间的是 $(2,1,3)$ 和 $(2,3,1)$，共 $2$ 个。

输入示例 2

5
5 4 2 1 3
5 1 2 3 4

输出示例 2

0

示例 2 说明

这里 $Q$ 的字典序其实比 $P$ 还小（第 $2$ 位 $1 < 4$），所以不存在夹在中间的排列，输出 $0$。注意题目并没有保证 $P < Q$。

输入示例 3

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

输出示例 3

223

示例 3 说明

$N = 7$ 时全部排列共 $7! = 5040$ 个。$P = (3,6,5,2,7,1,4)$ 的字典序排名与 $Q = (4,1,5,7,2,3,6)$ 的排名相差 $224$，减去 $P$ 自己这一个，得到夹在中间的有 $223$ 个。

这组数据说明：$N$ 稍大时答案会迅速变大，必须用排名相减而不是逐个枚举比较。

约束条件

• $1 \le N \le 10$
• $P$、$Q$ 都是 $(1, 2, \ldots, N)$ 的排列
• 所有输入值均为整数