Problem Brief

Count House Segments After Destruction

FULLTIMEOA

You are monitoring building density in a district of houses. The district is represented as a number line, and each house is located at an integer position.

You are given houses, an array containing the initial locations of all houses, and queries, an array containing the locations of houses destroyed in order. After each destroyed house, return the number of house segments remaining.

A house segment is one or more adjacent houses whose positions are consecutive integers and which do not have neighboring houses immediately outside the segment.

1Example 1

Input

houses = [1, 2, 3, 6, 7, 9], queries = [6, 3, 7, 2, 9, 1]

Output

[3, 3, 2, 2, 1, 0]

Explanation

Initially the house segments are [1, 2, 3], [6, 7], and [9]. Removing the houses in query order leaves 3, 3, 2, 2, 1, and then 0 segments.

2Example 2

Input

houses = [2, 4, 5, 6, 7], queries = [5, 6, 2]

Output

[3, 3, 2]

Explanation

After removing 5, the segments are [2], [4], and [6, 7]. After removing 6, the segments are [2], [4], and [7]. After removing 2, two segments remain.

Constraints

Limits and guarantees your solution can rely on.

All values in houses are distinct.
Every value in queries appears in houses, and all values in queries are distinct.