A factory assembly line is laid out as a single fixed sequence of n stations, each identified by a distinct integer ID, ordered from the first station a part visits to the last. Before each shift, the safety team publishes a list of station IDs that require inspection during that shift; every published ID is guaranteed to belong to some station on the line, and no ID is published twice. An inspection zone is a maximal run of consecutive stations along the line (in the fixed line order) that are all on the inspection list — a single un-flagged station anywhere breaks the run into two separate zones (or removes a would-be zone entirely if it stood alone).
Count how many separate inspection zones this shift's list creates.
n, the number of stations on the line.n space-separated distinct integers, the station IDs in line order (first station to last).m, the number of stations flagged for inspection this shift.m space-separated distinct integers, the flagged station IDs (each one is guaranteed to appear somewhere on line 2). This line is empty when m is 0.1 <= n <= 2*10^50 <= m <= n-10^9 <= each station ID <= 10^9, and all n station IDs are distinctm flagged IDs are distinct, and each one appears among the n station IDsExample 1
Input
4 1 2 3 4 2 2 4
Expected
2
Explanation
Stations in order are 1, 2, 3, 4. The inspection list is {2, 4}. Station 1 is unflagged; station 2 is flagged and starts a new zone (zone count 1); station 3 is unflagged, so that zone ends; station 4 is flagged and starts a second zone (zone count 2) because station 3 broke the run. There are two separate zones, so the answer is 2.
Example 2
Input
5 5 10 15 20 25 3 10 15 25
Expected
2
Explanation
Stations in order are 5, 10, 15, 20, 25. The inspection list is {10, 15, 25}. Station 5 is unflagged; stations 10 and 15 are both flagged and consecutive, forming one zone; station 20 is unflagged, breaking the run; station 25 is flagged and starts a second, separate zone. The answer is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →