No tag edit access

E. Two Permutations

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputRubik 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*_{1} = *a*_{1} + *d*, *c*_{2} = *a*_{2} + *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*_{1}, *i*_{2}, ..., *i*_{n} (1 ≤ *i*_{1} < *i*_{2} < ... < *i*_{n} ≤ *m*), that *a*_{1} = *b*_{i1}, *a*_{2} = *b*_{i2}, ..., *a*_{n} = *b*_{in}, 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2018 16:37:17 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|