HeapTwo HeapsDesign
Numbers arrive one at a time, and at any moment you may be asked for the median of everything seen so far. The median is the middle value of the sorted numbers, or the average of the two middle values when the count is even. Process a list of operations: add x inserts a number, and median reports the current median.
Input
Line 1: q, the number of operations. Next q lines: add x or median.
Output
For every median operation print the median with exactly one digit after the decimal point (like 3.0 or 2.5). A number is always added before the first median.
Constraints
1 <= q <= 10^4 -10^5 <= x <= 10^5
Example 1
Input
5 add 1 add 2 median add 3 median
Output
1.5 2.0
After 1 and 2 the median is 1.5; after adding 3 it is 2.