Problem G
Mette

Mette seeks the middle ground. In her daily work, she is confronted with a constant stream of new values. Therefore, she must sometimes update which value is most in the middle.

More precisely, Mette wants to hold onto the median $m$ of $n$ different values. The median is the value that divides the other values into two equal sized sets. More precisely, the median $m$ is the value that is greater than $\frac12(n-1)$ values and less than $\frac12(n-1)$ values. The median of $(1, 10, 2)$ is $2$.

When new pairs of values arrive, Mette must update the median. For example, if the new values are $8$ and $1000$, Mette must now consider $(1,10,2, 8,1000)$, and the new median is therefore $8$. If then $7$ and $21$ appear, the values are $(1,10,2,8,1000,7,21)$; however, the new median is still $8$:

Input

The first line contains the number $n$ of values. You can assume that $n$ is odd and $3\leq n\leq 49,999$. The next line contains the first three values $v_1,v_2,v_3$. Each of the following $\frac12(n-1)-1$ lines contains two new values: first $v_4$ and $v_5$, then $v_6$ and $v_7$, and so on. The last line contains $v_{n-1}$ and $v_ n$. All values $v_1,\ldots , v_ n$ are different, and we have $0\leq v_ i\leq 10^6$ for all $1\leq i\leq n$.

Output

Write $\frac12(n-1)$ lines. The $i$th line should be the median of $(v_1,\ldots , v_{2i+1})$ for $1\leq i \leq \frac12(n-1)$.

7
1 10 2
8 1000
7 21

2
8
8

3
33 4 5

5