← 返回题目列表

AtCoder · arc151_e

E. 继续作为子串

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你一个整数序列 A = (A_1, A_2, \ldots, A_N) 长度 N。 此外,它的连续长度子序列 给出 P 和 Q : X = (X_1, X_2, \ldots, X_P) 和 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) 是 连续子序列 of A = (A_1, A_2, \ldots, A_N) 当有一个整数时 l 满意 1 \leq l \leq N-P+1 这样 X_i = A_{l+i-1} 对于每个 i = 1, 2, \ldots, P.

约束

  • 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

输出

打印答案。


样本输入 1

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

示例输出 1

3

你可以使 X 等于 Y 同时保持 X 的非空连续子序列 A,如下。

  1. 首先删除开头的元素 X。现在,你有 X = (1).
  2. 接下来,添加 5 结束时 X。现在,你有 X = (1, 5).
  3. 此外,添加 7 结束时 X。现在,你有 X = (1, 5, 7),等于 Y.

在这里,您执行三个操作,这是可能的最少操作。


示例输入 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

示例输出 2

7