Two Permutations

3000ms

262144K

Description:

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 a_i.

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 (c₁ = a₁ + d, c₂ = a₂ + d, ..., c_n = a_n + d) of length n is a subsequence of b.

Sequence a is a subsequence of sequence b, if there are such indices i₁, i₂, ..., i_n (1 ≤ i₁ < i₂ < ... < i_n ≤ m), that a₁ = b_i₁, a₂ = b_i₂, ..., a_n = b_{i_n}, 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.

Input:

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.

Output:

On a single line print the answer to the problem.

Sample Input:

1 1
1
1

Sample Output:

Sample Input:

1 2
1
2 1

Sample Output:

Sample Input:

3 3
2 3 1
1 2 3

Sample Output:

Informação

Provedor Codeforces

Código CF213E