623. Finding the median in a continuous stream of integers

0

Medium

Given a continuous stream of n integers, your task is to efficiently find the median of the elements read so far. All numbers in the stream are unique. Print only the integer part of the median.

Input Format

The first line contains an integer t, representing the number of test cases. Each test case consists of the following input: The first line contains an integer n, which represents the length of the data stream. The next line contains n space-separated integers.

Output Format

Print the effective median of the running data stream.

Example

Input

1 6 5 15 1 3 2 8

Output

5 10 5 4 3 4

Constraints

1 < t < 100
1< n < 10000
Loading...

View Submissions

Console