The past that is gone, don't look back at it, the past that is gone.
--- Lost Lamb

Background

In the fields of data analysis and algorithms, the median is a very important statistical indicator that reflects the central tendency of a dataset. It performs well in handling outliers, unlike the mean which is easily affected. In practical applications such as financial analysis, medical research, and quality control, there is often a need to dynamically calculate the median of a data stream, especially when new data is continuously arriving.

This task involves calculating the median of the first few odd-numbered items based on a growing sequence. Imagine a real-time monitoring system that receives a series of non-negative integer data. The system needs to immediately calculate and output the median after receiving each odd-numbered item, so that it can make quick responses and adjustments. The core of this problem is how to efficiently find the median of a dynamic data stream, especially when the amount of data is very large.

Problem Description

Given a sequence of non-negative integers $A$ of length $N$, calculate and output the median of the current odd-numbered items each time a new odd-numbered item is added.

Input Format

• The first line contains a positive integer $N$, indicating the length of the sequence.
• The second line contains $N$ non-negative integers $A_{1}, A_{2}, \dots, A_{N}$, representing the elements in the sequence.

Output Format

Output $\lfloor \frac{N + 1}{2} \rfloor$ lines. The $i$-th line outputs the median of the sequence $A_{1}, A_{2}, \dots, A_{2i-1}$.

Sample #1

Sample Input #1

7
1 3 5 7 9 11 6

Sample Output #1

1
3
5
7

Sample #2

Sample Input #2

7
3 1 5 9 8 7 6

Sample Output #2

3
3
5
6

Hints

For 20% of the data, $N \le 100$;

For 40% of the data, $N \le 3000$;

For 100% of the data, $1 \le N \le 10^7$, $0 \le A_i \le 10^9$.