Running Median

You are given a stream of integers. For each incoming number, you need to output the median of the stream seen so far. The median of a list is defined to be the middle element when the list is sorted. If the list has an even number of elements, the median is defined as \(\frac{a + b}{2}\), where \(a\) and \(b\) are the two middle elements.

Your task is to maintain the data stream efficiently and output the median after each insertion.

inputFormat

The first line contains an integer \(T\), the number of test cases. For each test case, the first line contains an integer \(N\), the number of elements in the stream. The next line contains \(N\) space-separated integers, representing the elements in the order they are inserted into the data stream.

outputFormat

For each test case, print a single line of \(N\) numbers where the \(i\)-th number is the median after the \(i\)-th insertion. If the median is not an integer, print it as a floating point number.

1
5
5 15 1 3 2

5 10 5 4 3