#P8889. Harsh Sequence Cutting
Harsh Sequence Cutting
Harsh Sequence Cutting
Given a sequence \(a_1, a_2, \ldots, a_n\) and \(m\) distinct integers \(b_1, b_2, \ldots, b_m\), you are to perform a harsh cutting on the sequence.
For every index \(i\) with \(1 \le i \le n\), if there exists an index \(j\) with \(1 \le j \le m\) such that \(a_i = b_j\), index \(i\) is called a cut point. For every cut point, remove the number at that position and split the sequence into two parts at that position.
After performing all such cuts, determine the number of non-empty segments (pieces) produced. Note that if a cut occurs at the beginning or end of the sequence (i.e. when \(i=1\) or \(i=n\)), the non-existent segment adjacent to the boundary is not counted as a valid piece.
For clarity, consider that if there are no cut points, the entire sequence is one segment.
inputFormat
The input consists of three lines:
- The first line contains two integers \(n\) and \(m\) separated by a space.
- The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) separated by spaces.
- The third line contains \(m\) distinct integers \(b_1, b_2, \ldots, b_m\) separated by spaces.
outputFormat
Output a single integer representing the number of segments (pieces) remaining after all harsh cuts have been made.
sample
5 2
1 2 3 4 5
2 4
3