Design a structure that ingests integers from a stream and can report the **median** of everything seen so far at any time. The median is the middle value of the sorted sequence; for an even count it is the **average of the two middle values**.
The structure supports two operations:
- "addNum" — add an integer num to the stream. Returns null.
- "findMedian" — return the median of all integers added so far.
You are given the operations as two parallel arrays: operations[i] is the operation name and values[i] is its argument list ([num] for "addNum", [] for "findMedian"). Apply them in order and return an array holding each operation's return value (null for every "addNum").
For example ["addNum","addNum","findMedian","addNum","findMedian"] with [[1],[3],[],[2],[]] returns [null, null, 2, null, 2]: after adding 1 and 3 the median is (1 + 3) / 2 = 2; after also adding 2 the sorted stream is [1, 2, 3] with median 2.
"findMedian" is only called after at least one "addNum".
Example cases
- even then oddin operations = ["addNum","addNum","findMedian","addNum","findMedian"], values = [[1],[3],[],[2],[]]out [null,null,2,null,2]Median of {1,3} is (1+3)/2 = 2; adding 2 gives {1,2,3} with median 2.
- fractional medianin operations = ["addNum","addNum","addNum","addNum","findMedian"], values = [[1],[2],[3],[4],[]]out [null,null,null,null,2.5]Sorted {1,2,3,4}; the two middle values 2 and 3 average to 2.5.
Constraints
- 1 <= operations.length <= 10^4
- operations[i] is one of "addNum", "findMedian".
- -10^5 <= num <= 10^5 for every "addNum".
- findMedian is only called on a non-empty stream.
["addNum","addNum","findMedian","addNum","findMedian"]
[[1],[3],[],[2],[]]