现给你一个长度为 $n$的序列 $a_1,\cdots ,a_n$​和 $m$个互不相同的整数 $b_1,\cdots ,b_m$​。你需要按照这 $m$个数对序列 $a$进行狠狠地切割。

具体的，对于一个数字 $i\in [1,n]$，如果存在一个整数 $j\in [1,m]$，使得 $a_i=b_j$，则将位置 $i$称为一个切割点。对序列 $a$中的每一个切割点，我们在这个位置进行一次狠狠地切割。方法是，将该位置的数字去除，然后在这个位置将其左右的序列/片段一分两半。

如果对狠狠地切割的定义有疑问，可以参照「样例 #1」及「样例解释 #1」进行理解。

你需要计算，在进行了所有可能的狠狠地切割后，序列被切割为了多少片段。

特别的，如果在切割后，某一段内没有数组，那这一段不可被叫做片段。同样的，如果 $1$或 $n$为切割点，其与开头和结尾之间也不存在片段。

如果对片段的概念有疑问，可以参照「样例 #2」及「样例解释 #2」进行理解。

【输入格式】

第一行为两个整数，依次表示序列 $a$的长度 $n$和序列 $b$的长度 $m$。
第二行有 $n$个整数，第 $i$个整数表示 $a_i$。
第三行有 $m$个整数，第 $i$个整数表示 $b_i$。

【输出格式】

输出一个整数，代表狠狠地切割后的片段的个数。

【输入输出样例#1】

输入#1

6 2
3 4 3 5 2 6
5 4

输出#1

3

【输入输出样例#2】

输入#2

6 3
3 4 3 5 2 6
3 5 6

输出#2

2

【说明提示】

样例 1 解释

在狠狠地切割前，序列 $a$a

如下所示：$\begin{array}{cccccc}3& 4& 3& 5& 2& 6\end{array}$

​$\begin{array}{cccccc}3& \mathrm{\mid }& 3& \mathrm{\mid }& 2& 6\end{array}$

​$\begin{array}{ccccc}\stackrel{\text{片段 1}}{\overbrace{3}}& \mathrm{\mid }& \stackrel{\text{片段 2}}{\overbrace{3}}& \mathrm{\mid }& \stackrel{\text{片段 3}}{\overbrace{26}}\end{array}$

样例 2 解释

以下我们展示去除之后的序列：

$\begin{array}{cccccc}\mathrm{\mid }& 4& \mathrm{\mid }& \mathrm{\mid }& 2& \mathrm{\mid }\end{array}$

​$\begin{array}{ccccccc}\stackrel{\text{这个不是片段}}{\overbrace{\phantom{\mathrm{}}}}\mathrm{\mid }& \stackrel{\text{片段 1}}{\overbrace{4}}& \mathrm{\mid }& \stackrel{\text{这个不是片段}}{\overbrace{\phantom{\mathrm{}}}}& \mathrm{\mid }& \stackrel{\text{片段 2}}{\overbrace{2}}& \mathrm{\mid }\stackrel{\text{这个不是片段}}{\overbrace{\phantom{\mathrm{}}}}\end{array}$​

数据规模与约定

• 对于 $30\mathrm{\%}$的数据，保证 $a$序列中没有任何元素在 $b$中出现过。形式化的，$\mathrm{\forall }i\in [1,n],\mathrm{\forall }j\in [1,m],a_i\mathrm{\ne }{b}_j$。
• 对于 $100\mathrm{\%}$的数据，保证 $1\le n,m\le 5\times 10^5$，$-10^{18}\le a_i,b_i\le 10^{18}$，序列 $b$中的元素两两不同。

提示

本题输入规模较大，建议考虑使用较快的读入读出方式。

【解题思路】

先将$b$序列排序，便于后续查找。然后遍历 $a$序列,通过二分查找法判断是否在$b$序列中。存在即分割，循环计数

【代码样例】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5 * 1e5 + 5;
long long a[MAXN];
long long b[MAXN];
int n, m;

bool isdivide(long long x) {
	auto i = lower_bound(b + 1, b + m + 1, x) - b;
	if (x == b[i]) {
		return true;
	} else {
		return false;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
	}
	sort(b + 1, b + m + 1); //排序
	int t = 0;
	int cnt = 0; //计数
	for (int i = 1; i <= n; i++) {
		if (isdivide(a[i])) {
			if (t > 0) {
				cnt++;
				t = 0;
			}
		} else {
			t++;
		}
	}
	if (t > 0) {
		cnt++;
	}
	cout << cnt << endl;

}