题目描述

圣彼得堡动物园的北极熊 Menshykov 和 Uslada 以及基辅动物园的大象 Horace 不知从哪里弄到了许多木质方块。他们开始用这些方块搭建方块塔，把方块一个接一个往上叠。他们定义若干垂直叠放的方块塔排成一排叫做墙。墙可以由不同高度的方块塔组成。

Horace 是第一个搭好墙的人，他把自己的墙称为“大象”。这面墙由 $w$ 个方块塔组成。北极熊们也搭好了他们的墙，但没有给它命名。他们的墙由 $n$ 个方块塔组成。Horace 看着北极熊们的墙，想着：有多少个区间可以让他“看到一头大象”？如果在 $w$ 个连续方块塔组成的区间内，这些方块塔的高度序列与 Horace 的墙完全相同，那么 Horace 就能“看到一头大象”。为了能看到尽可能多的大象，Horace 可以整体抬高或降低他的大象墙；即使整体降低后墙的一部分位于地面以下也是允许的。

你的任务是统计 Horace 能“看到一头大象”的区间个数。

输入格式

第一行包含两个整数 $n$ 和 $w$，分别表示北极熊墙和大象墙的方块塔数量。
第二行包含 $n$ 个整数 $a_i$，表示北极熊们墙上的每个方块塔的高度。
第三行包含 $w$ 个整数 $b_i$，表示大象墙上每个方块塔的高度。

输出格式

输出一个整数，表示北极熊们的墙上有多少个区间可以让 Horace“看到一头大象”。

13 5
2 4 5 5 4 3 2 2 2 3 3 2 1
3 4 4 3 2

2

说明 / 提示

样例中的大象墙高度依次为 $3,4,4,3,2$。北极熊墙中第 $2$ 至第 $6$ 个方块塔的高度为 $4,5,5,4,3$，把大象墙整体抬高 $1$ 后与之完全相同；第 $9$ 至第 $13$ 个方块塔的高度为 $2,3,3,2,1$，把大象墙整体降低 $1$ 后与之完全相同。因此满足条件的区间共有 $2$ 个。

由 ChatGPT 5 翻译

3 3
1 132 3
2 1 3

0

5 1
8 71 1 24 2
31

5

原题图示

样例中的大象墙与北极熊的墙：

数据范围

（$1 \le n, w \le 2 \times 10^5$）

（$1 \le a_i \le 10^9$）

（$1 \le b_i \le 10^9$）