Powered Addition (Codeforces 1339C)
Tags: Greedy, bitmasks

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):
def solve(a):
    maxdiff = 0
    lastmax = a[0]
    for ni in range(1, len(a)):
        if a[ni] > lastmax:
            lastmax = a[ni]
        else:
            maxdiff = max(maxdiff, lastmax - a[ni])
    p = 0
    while maxdiff > 0:
        p += 1
        maxdiff //= 2
    return p
t = int(input())
ans = []
for ti in range(t):
    n = int(input())
    a = [int(x) for x in input().split()]
    ans.append(solve(a))
for a in ans:
    print(a)

Solution (Python):
for i in range(int(input())):
    (n, a) = (int(input()), list(map(int, input().split())))
    ans = 0
    for i in range(1, n):
        if a[i] < a[i - 1]:
            (ans, a[i]) = (max(len(bin(a[i - 1] - a[i])) - 2, ans), a[i - 1])
    print(ans)

Solution (Python):
def main_function():
    import sys
    input = sys.stdin.readline
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        current_max_num = a[0]
        max_difference = 0
        for el in a:
            if el < current_max_num:
                max_difference = max(max_difference, current_max_num - el)
            else:
                current_max_num = el
        if max_difference == 0:
            print(0)
        else:
            print(len(bin(max_difference)) - 2)
if __name__ == '__main__':
    main_function()