Median of BST from Level Order

Given the level order traversal of a balanced Binary Search Tree (BST), construct the BST and compute the median of its node values. The median is defined as the middle value in the sorted order. If the number of values is even, the median is the average of the two middle numbers. Formally, if the sorted array is (A) with (n) elements, the median (m) is given by [ m = \begin{cases} A_{\frac{n+1}{2}} & \text{if } n \text{ is odd},\ \frac{A_{\frac{n}{2}} + A_{\frac{n}{2}+1}}{2} & \text{if } n \text{ is even}. \end{cases} ]

You are given an array representing the level order traversal of the BST. Construct the BST using level order insertion and then perform an in-order traversal to retrieve the node values in sorted order. Finally, compute and output the median value with one digit after the decimal point.

inputFormat

The input begins with an integer (T) representing the number of test cases. For each test case, the first line contains an integer (N), the number of nodes in the BST. The next line contains (N) integers separated by spaces, representing the level order traversal of the BST.

outputFormat

For each test case, output a single line containing the median of the BST node values, printed with one digit after the decimal point.## sample

1
1
10

10.0