Process queue with wait limits

A single server works through a line of n processes in first-in, first-out order. Process i (0-indexed, in line order) can wait at most wait[i] seconds. Once that much time has passed, it gives up and leaves the line, even if it was never served.

The clock starts at t = 0 with all n processes in line. At every second t = 1, 2, 3, ... two things happen at the same moment:

1. The process at the front of the line is served and leaves.
2. Every process still in line with wait[i] <= t leaves because its limit has run out.

Implement:

def queue_sizes(wait: list[int]) -> list[int]:
    ...

Return the number of processes in line at t = 0, then after each second, up to and including the first second at which the line is empty.

Constraints

• 0 <= n <= 10^5
• 1 <= wait[i] <= 10^9
• Aim for better than O(n^2).

Example 1

wait = [3, 1, 2, 10]
output = [4, 2, 1, 0]

At t=1 the process with wait 3 is served and the one with wait 1 expires, leaving [2, 10]. At t=2 the 2 is served. At t=3 the 10 is served.

Example 2

wait = [5, 1, 1, 2]
output = [4, 1, 0]

At t=1 the 5 is served and both 1s expire. At t=2 the 2 is served, and the line is empty.