分数: 300 分
问题陈述
高桥的书架上有 N 书籍排成一排。的 i从左边算起的第本书上写有一个用整数表示的数字 A_i.
青木锯 M 书店橱窗里的书籍排成一排。的 j从左边算起的第本书上写有一个用整数表示的数字 B_j.
请注意,书号可能有重复。
确定高桥书架中是否存在与显示窗口中的排列完全匹配的连续子序列。
具体来说,判断是否存在整数 分别为 i (1 \le i \le N - M + 1)这样 A_i, A_{i+1}, \dots, A_{i+M-1} 匹配 B_1, B_2, \dots, B_M 。如果这样一个 i 存在,输出最小的这样 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
- 第一行包含高桥书架上的书籍数量 N 以及显示窗口中的图书数量 M,用空格分隔。
- 第二行包含高桥书架上每本书的编号 A_1, A_2, \dots, A_N,用空格分隔。
- 第三行包含显示窗口中每本书的编号 B_1, B_2, \dots, B_M,用空格分隔。
输出
一行输出最小整数 分别为 i 这样 A_i, A_{i+1}, \dots, A_{i+M-1} 匹配 B_1, B_2, \dots, B_M 。如果没有这样的 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