配点 : $700$ 点

問題文

長さ $N$ の整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。 また、$A$ の長さ $P$ の連続な部分列 $X = (X_1, X_2, \ldots, X_P)$ と、$A$ の長さ $Q$ の連続な部分列 $Y = (Y_1, Y_2, \ldots, Y_Q)$ が与えられます。

$X$ に対して、下記の $4$ つのいずれかを行うという操作を、好きな回数（ $0$ 回でも良い）だけ行うことができます。

• $X$ の先頭に任意の整数を $1$ つ追加する。
• $X$ の先頭の要素を削除する。
• $X$ の末尾に任意の整数を $1$ つ追加する。
• $X$ の末尾の要素を削除する。

ただし、各操作の前後において、$X$ は $A$ の空でない連続な部分列でなければなりません。 $X$ を $Y$ と一致させるために行う操作回数の最小値を求めてください。 なお、本問題の制約下において、操作の繰り返しによって $X$ と $Y$ を必ず一致させられることが証明できます。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• $1 \leq P, Q \leq N$
• $(X_1, X_2, \ldots, X_P)$ と $(Y_1, Y_2, \ldots, Y_Q)$ は、$(A_1, A_2, \ldots, A_N)$ の連続な部分列
• 入力はすべて整数

入力

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

$N$

$A_1$ $A_2$ $\ldots$ $A_N$

$P$

$X_1$ $X_2$ $\ldots$ $X_P$

$Q$

$Y_1$ $Y_2$ $\ldots$ $Y_Q$

出力

答えを出力せよ。

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

3

下記の手順で操作すると、$X$ が $A$ の空でない連続な部分列であるという条件を満たしたまま、$X$ を $Y$ に一致させることが出来ます。

1. まず、$X$ の先頭の要素を削除する。その結果、$X = (1)$ となる。
2. 次に、$X$ の末尾に $5$ を追加する。その結果、$X = (1, 5)$ となる。
3. さらに、$X$ の 末尾に $7$ を追加する。その結果、$X = (1, 5, 7)$ となり、$X$ は $Y$ と一致する。

上記の手順の操作回数は $3$ 回であり、これが考えられる最小の操作回数です。

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

7