# Track the Median of a Stream Design a data structure that accepts integers one at a time and returns the median of all values seen so far. The captured source describes the class-based "Find Median from Data Stream" problem. The top-level function below is a deterministic PracHub practice wrapper for console evaluation; it was not supplied verbatim by the source. You may implement this stateful class internally: ```python class MedianTracker: def add(self, value: int) -> None: ... def median(self) -> float: ... ``` The required console entry point is: ```python def run_median_tracker(operations: list[list[object]]) -> list[object]: ... ``` `operations` is a Python-literal/JSON-compatible array of commands. Process commands from left to right with one fresh, initially empty tracker, and append exactly one result for every command: - `["add", value]` inserts `value` and appends `None`. - `["median"]` appends the current median as a Python `float`. - `["median"]` on an empty tracker appends the string `"EMPTY"` and does not change the tracker. - Any unknown or malformed command appends the string `"ERROR"`, makes no state change, and processing continues. A command is malformed if it is not a list, has the wrong arity, or supplies an invalid value. An insertion value is valid only when it is a non-Boolean Python integer in the inclusive range `[-10**9, 10**9]`. The outer `operations` argument must be a list; otherwise, raise `ValueError` before processing any command. An empty operation list returns `[]`. For an odd number of values, the median is the middle value after sorting, converted to `float`. For an even number, it is the arithmetic mean of the two middle values, also returned as `float`. Example: ```python run_median_tracker([ ["median"], ["add", 5], ["add", 1], ["median"], ["add", 3], ["median"], ["add", True], ]) # ["EMPTY", None, None, 3.0, None, 3.0, "ERROR"] ``` ## Constraints and Clarifications - `0 <= len(operations) <= 200_000`. - Duplicates and negative values are allowed. - `MedianTracker.median()` should raise `ValueError` when called directly before any insertion; the practice wrapper maps that empty state to `"EMPTY"`. - Do not sort the entire history after each insertion. - Target `O(log n)` time per valid insertion and `O(1)` time per median query. - Use a method of averaging that does not overflow in languages with fixed-width integers. ## Hints - Maintain a partition in which every value on one side is no greater than every value on the other. - Choose structures that expose the boundary values efficiently. - State and test the size and ordering invariants after every insertion.