/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) と長さ M の整数列 B=(B_1,B_2,\ldots,B_M) が与えられます。
A が B の部分列であるか判定してください。つまり、 B から 0 個以上の要素を取り除いた後、残りの要素を元の順序で連結することで B を A と一致させることができるか判定してください。
制約
- 1\le N\le M\le 2\times 10^5
- 1\le A_i,B_i\le 10^9
- 入力される値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
出力
A が B の部分列であるならば Yes を、そうでないならば No を出力せよ。
入力例 1
3 5 3 1 4 3 6 1 1 4
出力例 1
Yes
B から B_2,B_4 を削除すると (3,1,4) となり、 A と一致させることができます。このことから A は B の部分列であることが分かるので、 Yes を出力してください。
入力例 2
2 3 5 4 4 7 5
出力例 2
No
B のどの要素を削除しても A と一致させることはできないので、 No を出力してください。
入力例 3
3 3 7 7 7 7 7 7
出力例 3
Yes
元から A と B が一致している場合も答えは Yes です。
入力例 4
5 8 1 3 4 5 4 1 4 1 3 2 4 5 4
出力例 4
Yes
Problem Statement
You are given a length-N integer sequence A=(A_1,A_2,\ldots,A_N) and a length-M integer sequence B=(B_1,B_2,\ldots,B_M).
Determine if A is a subsequence of B. In other words, determine if one can remove zero or more elements of B and concatenate the remaining elements without changing the order to make B coincide with A.
Constraints
- 1\le N\le M\le 2\times 10^5
- 1\le A_i,B_i\le 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
Output
Print Yes if A is a subsequence of B, and No otherwise.
Sample Input 1
3 5 3 1 4 3 6 1 1 4
Sample Output 1
Yes
Removing B_2 and B_4 from B yields (3,1,4), which coincides with A. Thus, A turns out to be a subsequence of B, so print Yes.
Sample Input 2
2 3 5 4 4 7 5
Sample Output 2
No
Removing any element from B does not yield A, so print No.
Sample Input 3
3 3 7 7 7 7 7 7
Sample Output 3
Yes
The answer is Yes even if A and B are originally equal.
Sample Input 4
5 8 1 3 4 5 4 1 4 1 3 2 4 5 4
Sample Output 4
Yes