Problem

In a Meta live monitoring pipeline, event counts arrive one integer at a time. Implement a data structure that supports inserting a new integer from the stream and returning the median of all values seen so far at any moment.

Formal Specification

Implement a function that processes a list of operations and returns the result for each median query.

• Input:
  • operations: a list of operations
  • Each operation is either:
    • {"op": "add", "value": x} where x is an integer
    • {"op": "median"}
• Output:
  • Return a list where each median query contributes the current median.
  • If the number of elements seen so far is odd, the median is the middle value.
  • If it is even, the median is the average of the two middle values.

Examples

Example 1

• Input: operations = [{"op": "add", "value": 5}, {"op": "median"}, {"op": "add", "value": 2}, {"op": "median"}, {"op": "add", "value": 10}, {"op": "median"}]
• Output: [5, 3.5, 5]
• Explanation: After values [5], median is 5; after [5, 2], median is (2 + 5) / 2 = 3.5; after [5, 2, 10], median is 5.

Example 2

• Input: operations = [{"op": "add", "value": -1}, {"op": "add", "value": -2}, {"op": "median"}]
• Output: [-1.5]
• Explanation: Sorted values are [-2, -1], so the median is (-2 + -1) / 2 = -1.5.

Constraints

• 1 <= len(operations) <= 10^5
• -10^9 <= value <= 10^9
• At least one value is added before every median query