Numbers arrive one at a time. After each insertion you must report the median of all values seen so far.

To keep the output a single unambiguous integer, the median is defined as follows on the current multiset sorted in non-decreasing order:

• If the current count is odd, the median is the single middle element.
• If the current count is even, the median is the sum of the two middle elements (not their average), which is always an integer.

Each reported value is uniquely determined by the values seen so far.

Input format

Line 1: an integer n, the number of values in the stream. Line 2: n space-separated integers given in arrival order.

Output format

n lines. Line i is the median (as defined above) after the first i values have been inserted.

Constraints

• 1 ≤ n ≤ 100000
• -1000000000 ≤ each value ≤ 1000000000

5
5 2 8 1 9

5
7
5
7
5

4
10 20 30 40

10
30
20
50