|Codeforces Round #131 (Div. 1)|
Rubik is very keen on number permutations.
A permutation a with length n is a sequence, consisting of n different numbers from 1 to n. Element number i (1 ≤ i ≤ n) of this permutation will be denoted as ai.
Furik decided to make a present to Rubik and came up with a new problem on permutations. Furik tells Rubik two number permutations: permutation a with length n and permutation b with length m. Rubik must give an answer to the problem: how many distinct integers d exist, such that sequence c (c1 = a1 + d, c2 = a2 + d, ..., cn = an + d) of length n is a subsequence of b.
Sequence a is a subsequence of sequence b, if there are such indices i1, i2, ..., in (1 ≤ i1 < i2 < ... < in ≤ m), that a1 = bi1, a2 = bi2, ..., an = bin, where n is the length of sequence a, and m is the length of sequence b.
You are given permutations a and b, help Rubik solve the given problem.
The first line contains two integers n and m (1 ≤ n ≤ m ≤ 200000) — the sizes of the given permutations. The second line contains n distinct integers — permutation a, the third line contains m distinct integers — permutation b. Numbers on the lines are separated by spaces.
On a single line print the answer to the problem.
2 3 1
1 2 3