#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Online Median - Classic Problems | Repovive

CLS61. Online Median

2s256 MB

Read numbers one by one. After each insertion, print the current median. When the count is even, print the lower of the two middle values.

Constraints

$1 \le n \le 2 \cdot 10^5$
$-10^9 \le x_i \le 10^9$

Input

\begin{array}{l} n \\ x_1 \quad x_2 \quad \ldots \quad x_n \end{array}

Output

\begin{array}{l} median_1 \\ median_2 \\ \vdots \\ median_n \end{array}

Samples

Input

5
5 1 9 3 7

Explanation

The sorted prefixes have lower medians 5, 1, 5, 3, and 5 after the five insertions.

Output

Input

4
-2 -2 10 0

Explanation

After each insertion, the lower middle value of the sorted prefix remains -2.

Output

-2
-2
-2
-2

Input

3
1 2 3

Explanation

Case 1

The sorted prefixes are

Case 2

[1]

Case 3

Case 4

[1, 2]

Case 5

, and

Case 6

[1, 2, 3]

Case 7

, so the lower medians are 1, 1, and 2.

Output

1
1
2

$1 \le n \le 2 \cdot 10^5$
$-10^9 \le x_i \le 10^9$

\begin{array}{l} n \\ x_1 \quad x_2 \quad \ldots \quad x_n \end{array}

\begin{array}{l} median_1 \\ median_2 \\ \vdots \\ median_n \end{array}