B - Order of Books on the Bookshelf Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君の本棚には N 冊の本が一列に並んでいます。左から i 番目の本には整数 A_i で表される番号が書かれています。

青木君は、ある書店のショーウィンドウで M 冊の本が一列に並んでいるのを見ました。左から j 番目の本には整数 B_j で表される番号が書かれています。

なお、本の番号は重複することもあります。

高橋君の本棚の中に、ショーウィンドウの並びと完全に一致する連続区間が存在するかどうかを調べてください。

すなわち、A_i, A_{i+1}, \dots, A_{i+M-1} がそれぞれ B_1, B_2, \dots, B_M と一致するような整数 i (1 \le i \le N - M + 1) が存在するか判定してください。存在する場合はそのような i のうち最小のものを、存在しない場合は -1 を出力してください。

制約

  • 1 \le M \le N \le 5 \times 10^5
  • 1 \le A_i \le 10^9 (1 \le i \le N)
  • 1 \le B_j \le 10^9 (1 \le j \le M)
  • 入力はすべて整数である

入力

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M
  • 1 行目には、高橋君の本棚の冊数 N と、ショーウィンドウの冊数 M がスペース区切りで与えられる。
  • 2 行目には、高橋君の本棚の各本の番号 A_1, A_2, \dots, A_N がスペース区切りで与えられる。
  • 3 行目には、ショーウィンドウの各本の番号 B_1, B_2, \dots, B_M がスペース区切りで与えられる。

出力

A_i, A_{i+1}, \dots, A_{i+M-1} がそれぞれ B_1, B_2, \dots, B_M と一致するような最小の整数 i を 1 行で出力してください。そのような i が存在しない場合は -1 を出力してください。

入力例 1

6 3
4 1 2 3 5 6
2 3 5

出力例 1

3

入力例 2

4 2
1 3 1 3
3 3

出力例 2

-1

入力例 3

18 5
5 1 2 1 2 3 4 1 2 3 4 5 1 2 3 4 6 7
1 2 3 4 5

出力例 3

8

入力例 4

46 10
100 200 300 400 500 100 200 300 999 888 777 666 555 444 333 222 111 123 234 345 42 84 126 168 210 252 294 336 378 420 42 84 126 168 210 999999937 1 2 3 4 5 6 7 8 9 10
42 84 126 168 210 252 294 336 378 420

出力例 4

21

入力例 5

1 1
1000000000
1000000000

出力例 5

1

Score : 300 pts

Problem Statement

Takahashi's bookshelf has N books lined up in a row. The i-th book from the left has a number written on it represented by the integer A_i.

Aoki saw M books lined up in a row in a bookstore's show window. The j-th book from the left has a number written on it represented by the integer B_j.

Note that book numbers may have duplicates.

Determine whether there exists a contiguous subsequence in Takahashi's bookshelf that exactly matches the arrangement in the show window.

Specifically, determine whether there exists an integer i (1 \le i \le N - M + 1) such that A_i, A_{i+1}, \dots, A_{i+M-1} match B_1, B_2, \dots, B_M respectively. If such an i exists, output the smallest such i. If it does not exist, output -1.

Constraints

  • 1 \le M \le N \le 5 \times 10^5
  • 1 \le A_i \le 10^9 (1 \le i \le N)
  • 1 \le B_j \le 10^9 (1 \le j \le M)
  • All input values are integers

Input

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M
  • The first line contains the number of books on Takahashi's bookshelf N and the number of books in the show window M, separated by a space.
  • The second line contains the numbers of each book on Takahashi's bookshelf A_1, A_2, \dots, A_N, separated by spaces.
  • The third line contains the numbers of each book in the show window B_1, B_2, \dots, B_M, separated by spaces.

Output

Output in one line the smallest integer i such that A_i, A_{i+1}, \dots, A_{i+M-1} match B_1, B_2, \dots, B_M respectively. If no such i exists, output -1.

Sample Input 1

6 3
4 1 2 3 5 6
2 3 5

Sample Output 1

3

Sample Input 2

4 2
1 3 1 3
3 3

Sample Output 2

-1

Sample Input 3

18 5
5 1 2 1 2 3 4 1 2 3 4 5 1 2 3 4 6 7
1 2 3 4 5

Sample Output 3

8

Sample Input 4

46 10
100 200 300 400 500 100 200 300 999 888 777 666 555 444 333 222 111 123 234 345 42 84 126 168 210 252 294 336 378 420 42 84 126 168 210 999999937 1 2 3 4 5 6 7 8 9 10
42 84 126 168 210 252 294 336 378 420

Sample Output 4

21

Sample Input 5

1 1
1000000000
1000000000

Sample Output 5

1