Median Finder from Number Stream

The median is the middle element in a sorted list of integers. If the list contains an even number of elements, the median is the average of the two middle elements.

For instance,

[4, 5, 6] has median 5

[7, 8] has median (7 + 8) / 2 = 7.5

Create a data structure that supports the following operations:

• insertNumber(int val) - Add an integer value from the input stream.
• getMedian() - Retrieve the median of all numbers added so far.

Examples

insertNumber(5)
insertNumber(10)
getMedian()  // Returns 7.5
insertNumber(3)
getMedian()  // Returns 5
    

Constraints

• Each input number will be between -10,000 and 10,000 inclusive.
• There will be at most 50,000 calls to insertNumber and getMedian combined.