CF1338A Powered Addition

You have an array $ a $ of length $ n $ . For every positive integer $ x $ you are going to perform the following operation during the $ x $ -th second: - Select some distinct indices $ i_{1}, i_{2}, \ldots, i_{k} $ which are between $ 1 $ and $ n $ inclusive, and add $ 2^{x-1} $ to each corresponding position of $ a $ . Formally, $ a_{i_{j}} := a_{i_{j}} + 2^{x-1} $ for $ j = 1, 2, \ldots, k $ . Note that you are allowed to not select any indices at all. You have to make $ a $ nondecreasing as fast as possible. Find the smallest number $ T $ such that you can make the array nondecreasing after at most $ T $ seconds. Array $ a $ is nondecreasing if and only if $ a_{1} \le a_{2} \le \ldots \le a_{n} $ . You have to answer $ t $ independent test cases.

N/A

N/A

In the first test case, if you select indices $ 3, 4 $ at the $ 1 $ -st second and $ 4 $ at the $ 2 $ -nd second, then $ a $ will become $ [1, 7, 7, 8] $ . There are some other possible ways to make $ a $ nondecreasing in $ 2 $ seconds, but you can't do it faster. In the second test case, $ a $ is already nondecreasing, so answer is $ 0 $ . In the third test case, if you do nothing at first $ 2 $ seconds and select index $ 2 $ at the $ 3 $ -rd second, $ a $ will become $ [0, 0] $ .