# What is the Median?

# 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`

) and total number of integers is no more than ^{31}**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.

1 3 4 60 70 50 2

1 2 3 3 4 27 4