CF1705B Mark the Dust Sweeper

Mark is cleaning a row of $ n $ rooms. The $ i $ -th room has a nonnegative dust level $ a_i $ . He has a magical cleaning machine that can do the following three-step operation. - Select two indices $ i

The first line contains a single integer $ t $ ( $ 1\leq t\leq 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 2\leq n\leq 2\cdot 10^5 $ ) — the number of rooms. The second line of each test case contains $ n $ integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 0\leq a_i\leq 10^9 $ ) — the dust level of each room. It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2\cdot 10^5 $ .

For each test case, print a line containing a single integer — the minimum number of operations. It can be proven that there is a sequence of operations that meets the goal.

In the first case, one possible sequence of operations is as follows. - Choose $ i=1 $ and $ j=2 $ , yielding the array $ [1,1,0] $ . - Choose $ i=1 $ and $ j=3 $ , yielding the array $ [0,1,1] $ . - Choose $ i=2 $ and $ j=3 $ , yielding the array $ [0,0,2] $ . At this point, $ a_1=a_2=0 $ , completing the process.In the second case, one possible sequence of operations is as follows. - Choose $ i=4 $ and $ j=5 $ , yielding the array $ [0,2,0,1,1] $ . - Choose $ i=2 $ and $ j=3 $ , yielding the array $ [0,1,1,1,1] $ . - Choose $ i=2 $ and $ j=5 $ , yielding the array $ [0,0,1,1,2] $ . - Choose $ i=3 $ and $ j=5 $ , yielding the array $ [0,0,0,1,3] $ . - Choose $ i=4 $ and $ j=5 $ , yielding the array $ [0,0,0,0,4] $ . In the last case, the array already satisfies the condition.