Powered Addition (Codeforces 1338A)
Tags: Greedy, math

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.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.The first line of each test case contains single integer $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — the length of array $$$a$$$. It is guaranteed that the sum of values of $$$n$$$ over all test cases in the input does not exceed $$$10^{5}$$$.The second line of each test case contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$-10^{9} \le a_{i} \le 10^{9}$$$).

Output: For each test case, print the minimum number of seconds in which you can make $$$a$$$ nondecreasing.

Note: 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]$$$.

Sample Inputs:
3
4
1 7 6 5
5
1 2 3 4 5
2
0 -4

Sample Outputs:
2
0
3

Solution (Python):
for s in [*open(0)][2::2]:
    A = [*map(int, s.split())]
    a = A[0]
    t = 0
    for i in A:
        if a > i:
            t = max(t, (a - i).bit_length())
        else:
            a = i
    print(t)

Solution (Python):
import bisect
B = [2 ** i for i in range(32)]
for s in [*open(0)][2::2]:
    A = [*map(int, s.split())]
    a = A[0]
    t = 0
    for i in A:
        if a > i:
            t = max(t, bisect.bisect(B, a - i))
        else:
            a = i
    print(t)

Solution (Python):
for s in [*open(0)][2::2]:
    A = [*map(int, s.split())]
    a = A[0]
    t = 0
    for i in A:
        t = max(t, max(a - i, 0).bit_length())
        a = max(a, i)
    print(t)