← 返回题目列表

Codeforces · 213/E

E. 两种排列

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

Rubik 非常热衷于数字排列。

长度为 n 的排列 a 是一个序列,由 1 到 n 的 n 个不同数字组成。该排列的元素编号 i (1 ≤ i ≤ n) 将表示为 ai。

Furik 决定向 Rubik 赠送礼物,并提出了一个关于排列的新问题。 Furik 告诉 Rubik 两个数字排列:长度为 n 的排列 a 和长度为 m 的排列 b。 Rubik 必须给出问题的答案:存在多少个不同的整数 d,使得长度为 n 的序列 c (c1 = a1 + d, c2 = a2 + d, ..., cn = an + d) 是 b 的子序列。

序列 a 是序列 b 的子序列,如果在 (1 ≤ i1 < i2 < ... < in ≤ m) 中存在索引 i1, i2, ..., ,则 a1 = bi1, a2 = bi2, ..., an = bin,其中 n 是序列 a 的长度,m 是序列 b 的长度。

给你排列 a 和 b,帮助 Rubik 解决给定的问题。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ m ≤ 200000) — 给定排列的大小。第二行包含 n 个不同的整数 - 排列 a,第三行包含 m 个不同的整数 - 排列 b。行上的数字用空格分隔。

输出

在一行上打印问题的答案。

示例

输入 #1

1 1
1
1

输出 #1

1

输入 #2

1 2
1
2 1

输出 #2

2

输入 #3

3 3
2 3 1
1 2 3

输出 #3

0