C - Between P and Q 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

整数 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 が存在して、下記の 2 つがともに成り立つ。
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
    • S_i が T_i より（数として）小さい。

制約

  • 1\le N\le 10
  • P,Q は (1,2,\ldots,N) を並び替えた整数列
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
P_1 P_2 \ldots P_N
Q_1 Q_2 \ldots Q_N

出力

答えを出力せよ。

入力例 1

3
1 3 2
3 1 2

出力例 1

2

(2,1,3),(2,3,1) の 2 つが条件を満たします。したがって、2 を出力してください。

入力例 2

5
5 4 2 1 3
5 1 2 3 4

出力例 2

0

条件を満たす (1,2,3,4,5) を並び替えた整数列は存在しません。

入力例 3

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

出力例 3

223

Score : 300 points

Problem Statement

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.

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.

Input

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

Output

Output the answer.

Sample Input 1

3
1 3 2
3 1 2

Sample Output 1

2

Two sequences (2,1,3),(2,3,1) satisfy the condition. Thus, output 2.

Sample Input 2

5
5 4 2 1 3
5 1 2 3 4

Sample Output 2

0

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

Sample Input 3

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

Sample Output 3

223