Find the Median - 2

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\le x<2^{31})$ and total number of integers is no more than $10^6$.

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.

Examples