The median of a finite list of numbers is the "middle" number, when those numbers are sorted. If the size of the list is even, the median is the average of the two middle numbers.

You have an incomming stream of integers, you need to be able to find the median at any point in time.

Implement the MedianCalculator class:

• MedianCalculator() initializes the MedianCalculator object and is called at the beginning.
• void addNum(int num) adds the integer num from the data stream.
• float getMedian() returns the median of all elements so far.

getMedian will be called only after atleast one number has been added.

Testing

Input Format

The first line contains an integer n denoting the number of function calls.

The second line has n space-separated numbers, where:

• If number is -999999, then its a call to getMedian().
• Otherwise, its a call to addNum(int num) with the number.

Output Format

Space-separated results of getMedian() accurate upto 1 decimal place.

Sample Input

8
2 -999999 1 -999999 5 -999999 4 -999999

Expected Output

2.0 1.5 2.0 3.0

1 <= n <= 5*105
-105 <= num <= 105