CF2255D How Long Until Nothing Remains?

Before her final sortie, Chtholly asks Willem three questions. The first is this: if the end is inevitable, how long will it take until nothing remains? Willem cannot answer her directly. Instead, he writes down $ n $ positive integers $ a_1,a_2,\ldots,a_n $ . Each operation takes one second. In one operation, Willem does the following: - Choose an index $ p $ ( $ 1\le p\le n $ ); - Then, replace $ a_p $ with $ \left\lfloor\dfrac{a_p}{2}\right\rfloor $ , and for every $ i\ne p $ , replace $ a_i $ by $ \left\lceil\dfrac{a_i}{2}\right\rceil $ . All replacements are performed simultaneously. Find the minimum number of seconds needed to make all $ n $ integers equal to $ 0 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 1\le n\le2\cdot10^5 $ ) — the number of integers. The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1\le a_i\le10^9 $ ) — the initial integers. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

For each test case, output a single integer — the minimum number of seconds needed to make all integers equal to $ 0 $ .

In the first test case, the only integer changes as $ 3\to1\to0 $ , so the answer is $ 2 $ . In the second test case, an integer equal to $ 1 $ becomes $ 0 $ only when its index is chosen. Thus, at least $ 3 $ seconds are necessary, and choosing every index once is sufficient. In the third test case, an optimal sequence is: 1. Choose $ p=1 $ : $ [1,2,4]\to[0,1,2] $ ; 2. Choose $ p=2 $ : $ [0,1,2]\to[0,0,1] $ ; 3. Choose $ p=3 $ : $ [0,0,1]\to[0,0,0] $ . In the fourth test case, an optimal sequence is $ [5,2]\to[2,1]\to[1,0]\to[0,0] $ , where the chosen indices are $ 1 $ , $ 2 $ , and $ 1 $ .