Find How Many Subarrays Match The Pattern

In the pattern, 1 means the next number is greater than the previous one, −1 means it is smaller, and 0 means they are equal. Given an array and a pattern of length m, count the contiguous subarrays of length m+1 whose adjacent comparisons all match; overlaps are allowed.

输入格式

This site's input: the first line contains n m (2≤n≤100000, 1≤m<n), the second line contains n integers (−10⁹..10⁹), and the third line contains m values, each −1, 0, or 1.

输出格式

Output the number of matching windows.

样例 1

输入：

8 3
4 1 3 4 4 5 5 1
1 0 -1

输出：

1

样例 2

输入：

4 2
2 2 2 2
0 0

输出：

2

样例 3

输入：

2 1
1 2
1

输出：

1

样例说明

Example 1: only [4,5,5,1], starting at index 4, goes up, stays flat, then goes down in order, so the answer is 1.

Example 2: the two length-3 windows starting at indices 0 and 1 are both all equal, and overlaps are allowed, so the answer is 2.

Example 3: the only window, 1,2, strictly increases and matches the pattern 1, so the answer is 1.