Powered Addition
Contest: Codeforces Round 633 (Div. 1)
Difficulty rating: 1500
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 format:
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 format:
For each test case, print the minimum number of seconds in which you can make $$$a$$$ nondecreasing.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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

Example input:
3
4
1 7 6 5
5
1 2 3 4 5
2
0 -4

Example output:
2
0
3

Editorial:
First, let's define $$$b$$$ as ideal destination of $$$a$$$, when we used operations.
Observation 1. Whatever you select any $$$b$$$, there is only one way to make it, because there is no more than single way to make specific amount of addition. That means we just have to select optimal destination of $$$a$$$.
For example, if you want to make $$$a_{1}$$$ from 10 to 21, then you must do $$$10 \to 11 \to 13 \to 21$$$. There is no other way to make $$$10$$$ to $$$21$$$ using given operations.
So now we have to minimize $$$max(b_{1} - a_{1}, b_{2} - a_{2}, \ldots, b_{n} - a_{n})$$$, as smaller differences leads to use shorter time to make $$$a$$$ nondecreasing.
Observation 2. $$$b$$$ is optimal when $$$b_{i}$$$ is the maximum value among $$$b_{1}, b_{2}, \ldots, b_{i-1}$$$ and $$$a_{i}$$$.
Because for each position $$$i$$$, we have to make $$$b_{i} - a_{i}$$$ as smallest possible. Since $$$b_{i}$$$ should be not smaller than previous $$$b$$$ values and also $$$a_{i}$$$, we derived such formula.
So from position $$$1, 2, \ldots, n$$$, greedily find a $$$b_{i}$$$, and check how many seconds needed to convert $$$a_{i}$$$ to $$$b_{i}$$$. The answer is maximum needed seconds among all positions.
Time complexity is $$$O(n)$$$, but you can do $$$O(n \log n)$$$ with "std::set" or whatever.