CodeForces-213E：Two Permutations（神奇的线段树+hash）

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_i1, a₂ = 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.

Example

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

题意：给定全排列A（1-N），全排列B（1-M），问有多少个d，满足全排列A的每一位+d后，是B的子序列（不是字串）。

思路：对于全排列A，得到hashA，先在B中得到1-N的hashB。每次d++的新排列，等效于1到N+1的排列每一位减去1（hash实现）。

具体的代码一看就明白。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int maxn=200010;
const int B=10007;
int N,M,pos[maxn],x;
ull g[maxn];
ull val,sum;
struct SegmentTree
{
    ull hash[maxn<<2];
    int cnt[maxn<<2];
    void build(int Now,int l,int r)
    {
        hash[Now]=cnt[Now]=0;
        if(l==r) return ;
        int mid=(l+r)>>1;
        build(Now<<1,l,mid);
        build(Now<<1|1,mid+1,r);
    }
    void pushup(int Now)
    {
        hash[Now]=hash[Now<<1]*g[cnt[Now<<1|1]]+hash[Now<<1|1];
        cnt[Now]=cnt[Now<<1]+cnt[Now<<1|1];
    }
    void update(int Now,int l,int r,int pos,int val,int num)
    {
        if(l==r)
        {
            hash[Now]+=num*val;
            cnt[Now]+=num;
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) update(Now<<1,l,mid,pos,val,num);
        else update(Now<<1|1,mid+1,r,pos,val,num);
        pushup(Now);
    }
}Tree;
int main()
{
    while(~scanf("%d%d",&N,&M))
    {
        val=sum=0;
        g[0]=1;
        for(int i=1;i<=N;i++)  g[i]=g[i-1]*B, sum+=g[i-1];
        for(int i=1;i<=N;i++){
            scanf("%d",&x);
            val=val*B+x;
        }
        for(int i=1;i<=M;i++){
            scanf("%d",&x);
            pos[x]=i;
        }
        Tree.build(1,1,M);
        int ans=0;
        for(int i=1;i<=M;i++)//把数值1~M按顺序加入线段树中
        {
            Tree.update(1,1,M,pos[i],i,1);
            if(i>=N)
            {
                if(Tree.hash[1]-(sum*(i-N))==val) ans++;
                Tree.update(1,1,M,pos[i-N+1],i-N+1,-1);
            }
        }
        printf("%d
",ans);
    }
    return 0;
}