Description

读入一个整数序列，每当读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

Input Format

第一行输入包含一个整数P，（1≤P≤1000），为测试数据的数量。

每个测试数据的第一行为一个奇数十进制整数M（1≤M≤9999），M为要处理的有符号整数的总数。

每个测试数据的第二行包含M个数

Output Format

对于每个数据集，在一行输出所有的中位数（输出的中位数个数应该是M加一的一半）。

3 
9 
1 2 3 4 5 6 7 8 9 
9 
9 8 7 6 5 4 3 2 1 
23 
23 41 13 22 -3 24 -31 -11 -8 -7 3 5 103 211 -311 -45 -67 -73 -81 -99 -33 24 56​

1 2 3 4 5
9 8 7 6 5
23 23 22 22 13 3 5 5 3 -3 -7 -3​

Source

堆