Dynamic Median Finder

You are given a stream of integers. Your task is to compute the median of the stream after all numbers have been added. The median is defined as follows:

If the number of elements, \(n\), is odd, the median is the middle element of the sorted stream. If \(n\) is even, the median is given by the formula:

$$\text{median} = \frac{x_{\frac{n}{2}} + x_{\frac{n}{2}+1}}{2}$$

You must read the input from standard input and write the result to standard output.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. Each test case consists of two lines:

• The first line contains an integer \(N\), the number of elements in the stream.
• The second line contains \(N\) space-separated integers.

outputFormat

For each test case output the median of the given numbers on a separate line. If \(N\) is even, output the median as a floating-point number (using the formula $$\frac{x_{\frac{n}{2}} + x_{\frac{n}{2}+1}}{2}$$), otherwise output the middle element as a floating-point number.

1
5
1 2 3 4 5

3.0