题目描述

给定整数 $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=(S_1,S_2,\ldots,S_{|S|})$ 比整数列 $T=(T_1,T_2,\ldots,T_{|T|})$ 字典序更小，是指以下 1. 和 2. 中任意一项成立。这里，$|S|,|T|$ 分别表示 $S,T$ 的长度。

1. $|S| \lt |T|$ 且 $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$。
2. 存在某个整数 $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$，使得以下两点同时成立：
   • $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$
   • $S_i$ 比 $T_i$（作为数字）更小。

输入格式

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

$N$
$P_1$ $P_2$ $\ldots$ $P_N$
$Q_1$ $Q_2$ $\ldots$ $Q_N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3
1 3 2
3 1 2

输出 #1

2

输入输出样例 #2

输入 #2

5
5 4 2 1 3
5 1 2 3 4

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

223

说明/提示

样例解释 1

$(2,1,3),(2,3,1)$ 这 $2$ 个满足条件。因此输出 $2$。

样例解释 2

不存在满足条件的 $(1,2,3,4,5)$ 的排列。

约束条件

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