[入门赛 #7] 狠狠地切割 (Hard Version)

**本题与 H1 的题意完全一致，区别仅在数据范围。在语言月赛中不存在 H2 题目，本题仅用于增加公开赛的区分度，并不严格遵循比赛考察范围，请酌情完成。**

现给你一个长度为 $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$。

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

6 2
3 4 3 5 2 6
5 4

3

6 3
3 4 3 5 2 6
3 5 6

2

### 样例 1 解释 在**狠狠地切割**前，序列 $a$ 如下所示： $$\begin{matrix} 3 & 4 & 3 & 5 & 2 & 6 \end{matrix}$$ 容易知道，第二个位置和第四个位置为切割点，我们使用 `|` 对其进行替换，代表去除工作： $$\begin{matrix} 3 & | & 3 & | & 2 & 6 \end{matrix}$$ 我们将片段进行简单的标记： $$\begin{matrix} \overbrace{3} ^ \text{片段 1} & | & \overbrace{3} ^ \text{片段 2} & | & \overbrace{2 \quad 6} ^ \text{片段 3} \end{matrix}$$ 共计 $3$ 个片段。 ### 样例 2 解释 以下我们展示去除之后的序列： $$\begin{matrix} | & 4 & | & | & 2 & | \end{matrix}$$ 我们将片段进行简单的标记： $$\begin{matrix} \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段} | & \overbrace{4} ^ \text{片段 1} & | & \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段} & | & \overbrace{2} ^ \text{片段 2} & | \overbrace{\vphantom{0}} ^ \text{\color{red}这个不是片段}\end{matrix}$$ 共计 $2$ 个片段。 ### 数据规模与约定 - 对于 $30\%$ 的数据，保证 $a$ 序列中没有任何元素在 $b$ 中出现过。形式化的，$\forall i \in [1, n], \forall j \in [1, m], a _ i \neq b _ j$。 - 对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 5 \times 10 ^ 5$，$- 10 ^ {18} \leq a _ i, b_i \leq 10 ^ {18}$，序列 $b$ 中的元素两两不同。 ### 提示 本题输入规模较大，建议考虑使用较快的读入读出方式。