Problem Description

Given a sequence \( A \) of length \( N \) consisting of non-negative integers, find the median for the first odd number of terms.

Input Format

The first line contains a positive integer \( N \).

The second line contains \( N \) positive integers \( A_{1 \dots N} \).

Output Format

Output \(\lfloor \frac{N + 1}{2} \rfloor\) lines, where the \( i \)-th line is the median of \( A_{1 \dots 2i - 1} \).

Sample Input and Output

Sample Input #1

7
1 3 5 7 9 11 6

Sample Output #1

1
3
5
6

Sample Input #2

7
3 1 5 9 8 7 6

Sample Output #2

3
3
5
6

Notes

For 20% of the data, \( N \leq 100 \);

For 40% of the data, \( N \leq 3000 \);

For 100% of the data, \( 1 \leq N \leq 100000 \), \( 0 \leq A_i \leq 10^9 \).

见题面 Input 部分

见题面 Output 部分