Codeforces Round 131 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

hashing

strings

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Two Permutations

time limit per test

2 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-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/29/2024 15:08:28 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|