What is the Median?
Median plays an important role in the world of statistics. By definition, it is a value which divides an array into two equal parts. In this problem you are to determine the current median of some long integers.
Suppose, we have five numbers {1, 3, 6, 2, 7}. In this case, 3 is the median as it has exactly two numbers on its each side: {1, 2} and {6, 7}.
If there are even number of values like {1, 3, 6, 2, 7, 8}, only one value cannot split this array into equal two parts, so we consider the average of the middle values {3, 6}. Thus, the median will be (3 + 6) / 2 = 4.5. In this problem, you have to print only the integer part, not the fractional. As a result, according to this problem, the median will be 4.
Input
Consists of series of integers x (0 ≤ x < 2^31) and total number of integers is no more than 30000.
Output
For each input integer print in a separate line the current value of the median. For each median value print only its integer part.