AT_awtf2025_c Get Closer

There are balls with integers from $ 1 $ to $ N $ written on them. Specifically, there are $ A_i $ balls with integer $ i $ ( $ 1 \leq i \leq N $ ) written on them. Define $ S=A_1+A_2+\cdots+A_N $ . Here, it is guaranteed that $ S $ is a positive even number. Divide the $ S $ balls into $ S/2 $ pairs. The integers written on the two balls in a pair must be different. It can be proved that such pairing is possible under the constraints of this problem. For each pair, perform the following operation: - Let the integers written on the two balls be $ x $ and $ y $ ( $ x < y $ ). Replace the numbers written on these balls with $ x+0.5 $ and $ y-0.5 $ , respectively. After completing the operation for all pairs, let $ d $ be the maximum number of balls with the same number written on them. Find the minimum possible value of $ d $ . Solve $ T $ test cases for each input.

The input is given from Standard Input in the following format: > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ Each test case is given in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

For each test case, output the answer.

### Sample Explanation 1 Consider the first test case. Let $ (x,y) $ denote a pair of balls with integers $ x,y $ written on them. For example, if we pair as $ (1,3),(2,3),(2,4) $ , the numbers written on the balls after the operation are $ 1.5,2.5,2.5,2.5,2.5,3.5 $ . The maximum number of balls with the same number written on them is $ d=4 $ . On the other hand, if we pair as $ (1,2),(2,3),(3,4) $ , the numbers written on the balls after the operation are $ 1.5,1.5,2.5,2.5,3.5,3.5 $ . The maximum number of balls with the same number written on them is $ d=2 $ . $ d $ cannot be made smaller than $ 2 $ , so the answer is $ 2 $ . ### Constraints - $ 1 \leq T \leq 125000 $ - $ 2 \leq N \leq 250000 $ - $ 0 \leq A_i \leq 10^9 $ - $ S=A_1+A_2+\cdots+A_N $ is a positive even number. - $ A_i \leq S/2 $ - The sum of $ N $ over all test cases in each input does not exceed $ 250000 $ . - All input values are integers.