CF2021A Meaning Mean

Pak Chanek has an array $ a $ of $ n $ positive integers. Since he is currently learning how to calculate the floored average of two numbers, he wants to practice it on his array $ a $ . While the array $ a $ has at least two elements, Pak Chanek will perform the following three-step operation: 1. Pick two different indices $ i $ and $ j $ ( $ 1 \leq i, j \leq |a| $ ; $ i \neq j $ ), note that $ |a| $ denotes the current size of the array $ a $ . 2. Append $ \lfloor \frac{a_i+a_j}{2} \rfloor $ $ ^{\text{∗}} $ to the end of the array. 3. Remove elements $ a_i $ and $ a_j $ from the array and concatenate the remaining parts of the array. For example, suppose that $ a=[5,4,3,2,1,1] $ . If we choose $ i=1 $ and $ j=5 $ , the resulting array will be $ a=[4,3,2,1,3] $ . If we choose $ i=4 $ and $ j=3 $ , the resulting array will be $ a=[5,4,1,1,2] $ . After all operations, the array will consist of a single element $ x $ . Find the maximum possible value of $ x $ if Pak Chanek performs the operations optimally. $ ^{\text{∗}} $ $ \lfloor x \rfloor $ denotes the floor function of $ x $ , which is the greatest integer that is less than or equal to $ x $ . For example, $ \lfloor 6 \rfloor = 6 $ , $ \lfloor 2.5 \rfloor=2 $ , $ \lfloor -3.6 \rfloor=-4 $ and $ \lfloor \pi \rfloor=3 $

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 5000 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 50 $ ) — the length of the array $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of the array $ a $ . Do note that the sum of $ n $ over all test cases is not bounded.

For each test case, output a single integer: the maximum possible value of $ x $ after all numbers have been picked.

In the first test case, the array is initially $ a=[1,7,8,4,5] $ . Pak Chanek will perform the following operations: 1. Pick $ i=1 $ and $ j=2 $ , then $ a=[8,4,5,4] $ . 2. Pick $ i=3 $ and $ j=2 $ , then $ a=[8,4,4] $ . 3. Pick $ i=2 $ and $ j=3 $ , then $ a=[8,4] $ . 4. Pick $ i=1 $ and $ j=2 $ , then $ a=[6] $ . After all the operations, the array consists of a single element $ x=6 $ . It can be proven that there is no series of operations that results in $ x $ greater than $ 6 $ in the end.