Problem 107: Statistelks

(U.M. ACM Runoffs 2001, problem 7)

Description

The NRA is making a survey of all the elks in the world, and compiling statistics vital for conservation. Automatic remote sensors are left in places that elks frequent; every time a new elk comes within range of a sensor, the sensor measures the elk's weight and sends that new piece of data back by satellite to HQ.

At HQ, an enormous number of elk weights will be received sometimes very rapidly, over the 7 years that the statistic gathering is expected to take. Of course, the NRA can't wait 7 years for results, so the data collection program must be able to provide intermediate results almost instantly.

You are to write a program that receives a stream of elk weights (all positive integers), and as soon as each weight is received, it should print out the median of all the weights received so far. Efficiency is essential, as there may be as many as 100000 (10⁵) elks left in the world.

Input Format

The input will be a sequence of positive integers all separated by white-space (spaces, tabs, or newlines).

Output Format

The output must be a sequence of numbers, one for each input; the numbers must be the exact medians, printed always to one decimal place (i.e. outputs must end with .0 or .5), one output per line.

Limits

All elks weigh between 50 and 50000 pounds.
There will be no more than 100000 elks.

Definition

The median of a set of numbers is the number that would be in the middle of the list if they were sorted in ascending order. If there is an even number of numbers, the median is the mean of the two that would be closest to the middle of the sorted list.

Sample Input

Sample Output