AT_abc468_c.Between P and Q

You are given an integer $N$ and integer sequences $P=(P_1,P_2,\ldots, P_N)$ and $Q=(Q_1,Q_2,\ldots,Q_N)$, each of which is a permutation of $(1,2,\ldots,N)$.

Find the number of integer sequences that are a permutation of $(1,2,\ldots,N)$ and are lexicographically greater than $P$ and lexicographically less than $Q$.

What is lexicographic order for integer sequences?

For integer sequences $S = (S_1,S_2,\ldots,S_{|S|})$ and $T = (T_1,T_2,\ldots,T_{|T|})$, we say that $S$ is lexicographically smaller than $T$ if $1.$ or $2.$ below holds. Here, $|S|, |T|$ denote the lengths of $S, T$, respectively.

1. $|S| \lt |T|$ and $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$.
2. There exists an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ such that both of the following two conditions hold.
   • $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$
   • $S_i$ is (numerically) smaller than $T_i$.

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

求满足以下条件的整数序列的个数：该序列是 $(1,2,\ldots,N)$ 的一个排列，且字典序严格大于 $P$、严格小于 $Q$。

什么是整数序列的字典序？

对于整数序列 $S = (S_1,S_2,\ldots,S_{|S|})$ 和 $T = (T_1,T_2,\ldots,T_{|T|})$，若满足以下条件之一，则称 $S$ 字典序小于 $T$。其中 $|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$。

The input is given from Standard Input in the following format:

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

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

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

Output the answer.

输出答案。

Sample 1 Explanation:
Two sequences $(2,1,3),(2,3,1)$ satisfy the condition. Thus, output $2$.

Sample 2 Explanation:
There is no permutation of $(1,2,3,4,5)$ satisfying the condition.

Constraints

• $1\le N\le 10$
• $P$ and $Q$ are integer sequences that are permutations of $(1,2,\ldots,N)$.
• All input values are integers.

样例 1 解释：
有两个序列 $(2,1,3)$ 和 $(2,3,1)$ 满足条件。因此输出 $2$。

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

约束条件

• $1\le N\le 10$
• $P$ 和 $Q$ 是 $(1,2,\ldots,N)$ 的排列（即整数序列）。
• 所有输入值均为整数。