AT_arc151_e [ARC151E] Keep Being Substring

[problemUrl]: https://atcoder.jp/contests/arc151/tasks/arc151_e 長さ $ 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 $

答えを出力せよ。

### 制約 - $ 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 $ 回であり、これが考えられる最小の操作回数です。