Problem Description

You are given a sequence \(a\) of length \(n\) and \(m\) distinct integers \(b_1, \cdots, b_m\). You need to perform brutal cutting 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 cutting point. For each cutting point in the sequence \(a\), we perform a brutal cut at this position. The method is to remove the number at this position and split the sequence or segment on both sides of this position into two halves.

If you have doubts about the definition of brutal cutting, refer to "Sample #1" and "Sample Explanation #1" for understanding.

You need to calculate the number of segments the sequence is divided into after all possible brutal cuts.

Particularly, if a segment contains no numbers after cutting, it is not considered a segment. Similarly, if \(1\) or \(n\) is a cutting point, there is no segment between them and the start or end.

If you have doubts about the concept of segments, refer to "Sample #2" and "Sample Explanation #2" for understanding.

Input Format

The first line contains two integers, representing the length \(n\) of sequence \(a\) and the length \(m\) of sequence \(b\).
The second line contains \(n\) integers, where the \(i\)-th integer represents \(a_i\).
The third line contains \(m\) integers, where the \(i\)-th integer represents \(b_i\).

Output Format

Output a single integer, representing the number of segments after brutal cutting.

Sample Input and Output

Sample Input #1

6 2
3 4 3 5 2 6
5 4

Sample Output #1

3

Sample Input #2

6 3
3 4 3 5 2 6
3 5 6

Sample Output #2

2

Notes

Sample 1 Explanation

Before brutal cutting, the sequence \(a\) is as follows:

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

It is easy to see that the second and fourth positions are cutting points. We use | to represent the removal:

\[ \begin{matrix} 3 & | & 3 & | & 2 & 6 \end{matrix} \]

We mark the segments simply:

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

There are a total of 3 segments.

Sample 2 Explanation

Here is the sequence after removal:

\[ \begin{matrix} | & 4 & | & | & 2 & | \end{matrix} \]

We mark the segments simply:

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

There are a total of 2 segments.

Data Size and Constraints

• For 20% of the data, \(n, m \leq 10\).
• For 70% of the data, \(n, m \leq 5 \times 10^3\).
• For 100% of the data, \(1 \leq n, m \leq 5 \times 10^5\), \(1 \leq a_i, b_i \leq 5 \times 10^6\).

Hints

The input size is large, so consider using fast input and output methods.

见题面 Input 部分

见题面 Output 部分