Running Median

You are given a sequence of integers. As each integer is inserted into an initially empty list, the list is kept in sorted order, and you are required to determine the running median after each insertion. For an odd number of elements, the median is the middle element; for an even number of elements, the median is defined as \( \frac{a_{\frac{n}{2}-1} + a_{\frac{n}{2}}}{2} \), where the array is 0-indexed and sorted.

inputFormat

The input consists of two lines. The first line contains a single integer \( n \) (the number of elements). The second line contains \( n \) space-separated integers.

outputFormat

Output the running medians after each insertion as space-separated values on a single line. If the median is an integer, output it without a decimal point.

3
2 1 5

2 1.5 2