Singers stand in a fixed line, left to right, with heights heights[i] in centimetres. For the photo, the choir director wants every singer who stays in the line to be at least gap cm taller than the nearest remaining singer to their left. She can ask any singers to step out, but nobody may swap places.
Implement fewest_removals(heights: list[int], gap: int) -> int: the smallest number of singers who must step out.
fewest_removals([150, 152, 151, 160, 155, 158], 3) # 3 keep e.g. 150, 155, 158
fewest_removals([170, 170, 170], 1) # 2 equal heights never satisfy the gap
With gap = 1 this is exactly "keep a strictly increasing subsequence". An empty line needs 0 removals.
Constraints: 0 <= len(heights) <= 100_000, 1 <= heights[i] <= 10**9, 1 <= gap <= 10**9. The O(n²) "check every earlier singer" DP is too slow at this size; aim for O(n log n).
Show hint
for each possible length of a valid kept line, remember the smallest last height such a line can end with; those values are sorted. The longest line a singer of height h can extend is then found by binary search for the largest last height that is <= h - gap.