Problem3752--Two Permutations

3752: Two Permutations

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 256 MiB

SubmitSolved: 0Submit Num: 0StatisticsShowOff!

Description

time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

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.

Examples
Input
1 1
1
1
Output
1
Input
1 2
1
2 1
Output
2
Input
3 3
2 3 1
1 2 3
Output
0

Source/Category

 
Submit