Background

This problem has exactly the same statement as H1. The only difference is the constraints. In the Language Monthly Contest there is no H2 problem. This problem is only used to increase the distinction in the public contest, and it does not strictly follow the contest syllabus. Please solve it as you see fit.

Problem Description

You are given a sequence $a _ 1, \cdots, a _ n$ of length $n$, and $m$ pairwise distinct integers $b _ 1, \cdots, b _ m$. You need to perform a hard cut on the sequence $a$ according to these $m$ numbers.

Specifically, for a number $i \in [1, n]$, if there exists an integer $j \in [1, m]$ such that $a _ i = b _ j$, then position $i$ is called a cut point. For every cut point in the sequence $a$, we perform one hard cut at this position. The method is: remove the number at this position, and then split the sequence/segment on its left and right into two parts at this position.

If you are unsure about the definition of hard cut, you can refer to “Sample #1” and “Sample Explanation #1”.

You need to calculate: after performing all possible hard cuts, into how many segments the sequence is cut.

In particular, if after cutting, some part contains no numbers, then this part cannot be called a segment. Similarly, if $1$ or $n$ is a cut point, then there is also no segment between it and the beginning or the end.

If you are unsure about the concept of segments, you can refer to “Sample #2” and “Sample Explanation #2”.

Input Format

The first line contains two integers, representing the length $n$ of sequence $a$ and the length $m$ of sequence $b$, respectively.
The second line contains $n$ integers, where the $i$-th integer is $a_i$.
The third line contains $m$ integers, where the $i$-th integer is $b_i$.

Output Format

Output one integer, representing the number of segments after hard cutting.

6 2
3 4 3 5 2 6
5 4

3

6 3
3 4 3 5 2 6
3 5 6

2

Hint

Sample 1 Explanation

Before the hard cut, the sequence $a$ is as follows:

$$\begin{matrix} 3 & 4 & 3 & 5 & 2 & 6 \end{matrix}$$

It is easy to see that the second position and the fourth position are cut points. We use | to replace them, representing the removal:

$$\begin{matrix} 3 & | & 3 & | & 2 & 6 \end{matrix}$$

We mark the segments briefly:

$$\begin{matrix} \overbrace{3} ^ \text{Segment 1} & | & \overbrace{3} ^ \text{Segment 2} & | & \overbrace{2 \quad 6} ^ \text{Segment 3} \end{matrix}$$

There are $3$ segments in total.

Sample 2 Explanation

Below we show the sequence after removal:

$$\begin{matrix} | & 4 & | & | & 2 & | \end{matrix}$$

We mark the segments briefly:

$$\begin{matrix} \overbrace{\vphantom{0}} ^ \text{\color{red}This is not a segment} | & \overbrace{4} ^ \text{Segment 1} & | & \overbrace{\vphantom{0}} ^ \text{\color{red}This is not a segment} & | & \overbrace{2} ^ \text{Segment 2} & | \overbrace{\vphantom{0}} ^ \text{\color{red}This is not a segment}\end{matrix}$$

There are $2$ segments in total.

Constraints

• For $30\%$ of the testdata, it is guaranteed that no element in sequence $a$ appears in $b$. Formally, $\forall i \in [1, n], \forall j \in [1, m], a _ i \neq b _ j$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 5 \times 10 ^ 5$, $- 10 ^ {18} \leq a _ i, b_i \leq 10 ^ {18}$, and the elements in sequence $b$ are pairwise distinct.

Hint

The input size of this problem is large, so it is recommended to use faster input/output methods.

Translated by ChatGPT 5