Leftmost-Fit Memory Allocator: Allocate Consecutive Units and Free by Owner

You manage a memory of `n` units, indexed `0` to `n - 1`, all free at the start. Process a list of operations in order, each of which produces one recorded value: - **Allocate** `[1, size, owner]`: find the leftmost block of `size` consecutive free units. If one exists, assign every unit of that block to `owner` and record the index of the block's first unit. If none exists, change nothing and record `-1`. - **Free** `[2, owner]`: free every unit currently assigned to `owner`, and record how many units were freed (`0` if the owner holds nothing). Return the list of recorded values, one per operation, in order. ### Function Signature ```python def run_allocator(n: int, operations: list[list[int]]) -> list[int]: ``` ### Rules - "Leftmost" means the block whose first unit has the smallest index among all runs of `size` consecutive free units. The block may start anywhere inside a longer free run; only its first unit's index matters. - An owner may hold several separate blocks at the same time, from several allocations. A free releases all of them. - Allocating for an owner that already holds units is allowed and does not affect the units it already holds. - After a free, the same owner ID may allocate again. ### Constraints - `1 <= n <= 100000` - `1 <= len(operations) <= 100000` - Each allocate operation is `[1, size, owner]` with `1 <= size <= n` and `1 <= owner <= 100000`. - Each free operation is `[2, owner]` with `1 <= owner <= 100000`. - Each recorded value is `-1` or an integer from `0` to `n`, so all values fit easily in 32-bit integers. - The interviewer expected each operation to take time logarithmic in `n`, amortized over the units freed; an approach that scans the whole memory on every operation is too slow at the upper limits. ### Examples **Example 1** - Input: `n = 8`, `operations = [[1, 3, 1], [1, 2, 2], [1, 2, 3], [2, 2], [1, 3, 4], [1, 2, 5], [2, 1], [1, 4, 6]]` - Output: `[0, 3, 5, 2, -1, 3, 3, -1]` - Explanation: Owner 1 takes units 0 to 2, owner 2 takes 3 to 4, and owner 3 takes 5 to 6. Freeing owner 2 releases 2 units. No run of 3 free units exists (the free runs are units 3 to 4 and unit 7), so owner 4 gets `-1`. Owner 5 takes units 3 to 4. Freeing owner 1 releases 3 units. The free runs are now units 0 to 2 and unit 7, so a block of 4 does not fit. **Example 2** - Input: `n = 5`, `operations = [[1, 2, 7], [1, 1, 9], [1, 2, 7], [2, 7], [1, 5, 1]]` - Output: `[0, 2, 3, 4, -1]` - Explanation: Owner 7 ends up holding two separate blocks, units 0 to 1 and units 3 to 4, and freeing owner 7 releases all 4 units. Unit 2 still belongs to owner 9, so a block of 5 does not fit. **Example 3** - Input: `n = 1`, `operations = [[2, 3], [1, 1, 3], [1, 1, 4], [2, 3], [1, 1, 4]]` - Output: `[0, 0, -1, 1, 0]` - Explanation: Freeing an owner that holds nothing records `0`. After owner 3 frees its unit, owner 4 can take unit 0.