Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

【题目背景】

zzy 是一场比赛的出题人,因为被验题人叫错名字而怒发冲冠,于是决心整一道超级 无解的题来恶心自己,并疯狂消费来下定自己的决心。不过这并不是那道题。

【题目描述】

现在 zzy 正在旅行中寻找灵感,突然发现自己的数据的出国啦!

已知国外有依次排列的 $m(1\le m\le 3\times 10^3)$ 个数据,称为序列 b;而 zzy 想要快点 找到他的数据,所以在脑中回忆了 $n(1\le n\le 10^6)$ 个数据,称为序列 a 。现在 zzy 准备动身了,他将从 $b_1$ 到 $b_m$ 依次寻找出国的 $m$ 个数据,只有他所找到的数据符合脑中数据的一个连续段(也就是 a 中的一个子区间),那么这次寻找就是成功的。

由于 zzy 想节省时间,他可以跳过 b 中的一个区间(区间长度可以为 0,但是不能等 于 m)。虽然这样不能找完所有的数据,但是验题人的催促更令人心急如焚。 请你求出所有可能的 zzy 能成功的方案数。(两个成功方案是不同的,当且仅当选择 跳过的区间左右端点不全相同,或者符合的连续段左右端点不全相同)

【输入格式】

从文件 happinon.in 中读入数据。 第一行两个整数 n, m ) 第二行一个长度为 n 的序列,表示 $a_1\sim a_n$。

第三行一个长度为 m 的序列,表示 $b_1\sim b_n$>

【输出格式】

输出到文件 happinon.out 中。 一行一个整数,表示所有可能的成功方案数 ans。

【样例输入 1】

5 3

1 2 1 1 2

1 3 2

【样例输出 1】

7

【样例输入 2】

8 4

1 2 1 1 2 1 1 2

1 2 1 1

【样例输出 2】

25