题目描述

给定一个长度为 $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$ 进行如下四种操作中的任意一种，每种操作可以执行任意次数（也可以不执行）：

• 在 $X$ 的开头添加任意一个整数。
• 删除 $X$ 的开头元素。
• 在 $X$ 的末尾添加任意一个整数。
• 删除 $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$，使得对于所有 $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

输入

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

输出

3

样例 2

输入

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)$ 的连续子序列
• 输入均为整数

样例解释 1

可以按如下步骤操作，使 $X$ 始终为 $A$ 的非空连续子序列，并最终变为 $Y$：

1. 首先删除 $X$ 的开头元素，结果 $X = (1)$。
2. 然后在 $X$ 的末尾添加 $5$，结果 $X = (1, 5)$。
3. 再在 $X$ 的末尾添加 $7$，结果 $X = (1, 5, 7)$，此时 $X$ 与 $Y$ 相同。

上述操作共需 $3$ 次，这就是最小操作次数。

由 ChatGPT 4.1 翻译