题目描述

長さ $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$ を必ず一致させられることが証明できます。

連続な部分列とは？ 数列 $X\ =\ (X_1,\ X_2,\ \ldots,\ X_P)$ が数列 $A\ =\ (A_1,\ A_2,\ \ldots,\ A_N)$ の連続な部分列であるとは、$1\ \leq\ l\ \leq\ N-P+1$ を満たす整数 $l$ が存在して、 すべての $i\ =\ 1,\ 2,\ \ldots,\ P$ について、$X_i\ =\ A_{l+i-1}$ が成り立つことです。

输入格式

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

$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $P$ $X_1$ $X_2$ $\ldots$ $X_P$ $Q$ $Y_1$ $Y_2$ $\ldots$ $Y_Q$

输出格式

答えを出力せよ。

题目大意

有一个序列 $A$。$X,Y$ 是给定的 $A$ 的两个子串，每次可以在 $X$ 的开头或末尾增添或删除一个数字，且需满足任意时刻 $X$ 非空且为 $A$ 的子串，求把 $X$ 变成 $Y$ 的最少次数。

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

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

提示

制約

• $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)$ の連続な部分列
• 入力はすべて整数

Sample Explanation 1

下記の手順で操作すると、$X$ が $A$ の空でない連続な部分列であるという条件を満たしたまま、$X$ を $Y$ に一致させることが出来ます。 1. まず、$X$ の先頭の要素を削除する。その結果、$X\ =\ (1)$ となる。 2. 次に、$X$ の末尾に $5$ を追加する。その結果、$X\ =\ (1,\ 5)$ となる。 3. さらに、$X$ の 末尾に $7$ を追加する。その結果、$X\ =\ (1,\ 5,\ 7)$ となり、$X$ は $Y$ と一致する。 上記の手順の操作回数は $3$ 回であり、これが考えられる最小の操作回数です。