6108 - 子序列(2)

题目描述

给定两个整数序列 A 和 B,请判断序列 B 是否是序列 A 的一个子序列。

一个序列 B 是序列 A 的子序列,当且仅当可以从 A 中删除若干个元素(也可以不删除),使得剩下的元素按照原有顺序恰好构成序列 B。

需要注意:

  • 删除元素时,不能改变剩余元素的相对顺序;
  • 子序列不要求连续,但必须保持顺序一致。

请你判断 B 是否为 A 的子序列。

输入

第 1 行读入两个整数 n, m,表示整数序列 A 和 B 的长度。

第 2 行包含 n 个整数,表示序列 A。

第 3 行包含 m 个整数,表示序列 B。

输出

输出一行一个字符:

  • 如果 B 是 A 的子序列,输出 Y。
  • 否则输出 N。
样例

输入

5 3
1 3 5 7 9
3 7 9

输出

Y

输入

5 3
1 3 5 7 9
3 9 7

输出

N

输入

6 4
2 1 2 3 2 1
1 2 1 2

输出

N
说明

样例说明 1

在序列 A 中选择第 2,4,5 个元素,得到序列:

3 7 9

与序列 B 完全一致,因此输出 Y。

样例说明 2

虽然 3 和 9 都在序列 A 中,但在 A 中 9 出现在 7 之后,无法保持顺序匹配,因此输出 N。

数据范围

对于 50\% 的数据,保证 1 \le n, m \le 1000。

对于 100\% 的数据,保证 1 \le n, m \le 10^5,A B 序列中的元素的值,均在 [1,10^9] 范围内。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 186
通过人数 115
金币数量 1 枚
难度 入门


上一题 下一题