The median of a list of numbers is defined as the middle value in a sorted list. When the list has an even number of elements, the median is the average of the two middle values.

For example:

• For the list [1, 2, 3], the median is 2
• For the list [1, 2], the median is (1 + 2) / 2 = 1.5

Implement a NumberStream class with the following methods:

• add(num: number): void: Adds an integer num to the data structure
• getMedian(): number: Returns the median of all numbers added so far

Input

The NumberStream instance will have its methods called with various parameters based on these:

• methods: string[]: An array of NumberStream method names
• params: (number | null)[]: An array of integers

methods[i] will be called with params[i].

Input: methods = ["add","getMedian"], params = [4,null]
Output: [null,4]
Explanation: Add 4 to the stream, then find the median, which is 4.

Input: methods = ["add","add","getMedian"], params = [10,20,null]
Output: [null,null,15]
Explanation: Add 10 and 20 to the stream. The median of [10, 20] is (10 + 20) / 2 = 15.

Input: methods = ["add","add","add","getMedian"], params = [1,2,3,null]
Output: [null,null,null,2]
Explanation: Add 1, 2, 3 to the stream. The median of [1, 2, 3] is 2.

Constraints

• 1 <= num <= 100,000
• 1 <= methods.length <= 1000
• There will be at least one element in the data structure before calling getMedian()