Answer Running Median Queries Over a Stream of Inserted Integers

Integers arrive one at a time, and at any point you may be asked for the median of every integer received so far. Process a sequence of operations and return the answer to each median query. Operation `i` is described by `operations[i]` and `values[i]`: - `"add"`: insert `values[i]` into the collection. - `"median"`: report the median of all integers inserted so far. For this operation `values[i]` is `0` and is ignored. The median of the collection is its middle value after sorting in non-decreasing order. With an even count it is the arithmetic mean of the two middle values. ### Function Signature ```python def median_stream(operations: list[str], values: list[int]) -> list[float]: ``` ### Rules - Return one float per `"median"` operation, in the order those operations appear. If there are no `"median"` operations, return an empty list. - Return every median as a float, including whole numbers (for example `10.0`). Every median is exactly an integer or an integer plus one half, so no rounding is involved. - Duplicate values count separately, and inserted values are never removed. ### Constraints - `1 <= len(operations) == len(values) <= 5 * 10^4` - Each `operations[i]` is exactly `"add"` or `"median"`. - `-10^5 <= values[i] <= 10^5` - Every `"median"` operation is preceded by at least one `"add"` operation. ### Examples **Example 1** - Input: `operations = ["add", "add", "median", "add", "median"]`, `values = [5, 15, 0, 1, 0]` - Output: `[10.0, 5.0]` - Explanation: after inserting 5 and 15 the median is `(5 + 15) / 2 = 10.0`. After inserting 1 the sorted collection is `[1, 5, 15]`, so the median is `5.0`. **Example 2** - Input: `operations = ["add", "median", "add", "median", "add", "add", "median"]`, `values = [-4, 0, -4, 0, 7, 2, 0]` - Output: `[-4.0, -4.0, -1.0]` - Explanation: at the three queries the sorted collections are `[-4]`, `[-4, -4]` and `[-4, -4, 2, 7]`; the last median is `(-4 + 2) / 2 = -1.0`.