If all elements of \(A\) are \(0\), the answer is \(0\). From here on, consider the case where a non-zero element exists.

Each operation decreases the value of \(A_i-2A_{i+1}\) by \(0\) or \(1\). Therefore, if there exists an \(i\) such that \(A_i-2A_{i+1}<0\), the answer is -1, and we obtain \(\displaystyle\max_i (A_i-2A_{i+1})\) as a lower bound on the answer.

Moreover, since a non-zero element exists, we obtain a lower bound \(\displaystyle\max\left(1,\max_i (A_i-2A_{i+1})\right)\).

Furthermore, this lower bound can actually be achieved.

Let \(\displaystyle D_i=A_i-2A_{i+1}\) and \(K=\max_i D_i\).

If \(K=0\), the answer is clearly \(1\), since setting \(x_0=A_1\) makes all elements of \(A\) equal to \(0\). From here on, consider the case \(K\geq 1\).

Construct \(X=(X_1,X_2,\ldots,X_K)\) as follows:

• Set \(X=(0,0,\ldots,0)\).
• For \(i=1,2,\ldots,N-1\) in order, do the following:
  • Add \(2^{i-1}\) to each of \(X_1,X_2,\ldots,X_{D_i}\).
• Add \(A_N\) to \(X_1\).

Then, choosing \(x_0=X_i\) on the \(i\)-th operation achieves the goal in \(K\) operations.

Sample implementation (Python3)

import sys

input = sys.stdin.readline


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    if max(a) == 0:
        return 0
    ans = 1
    for i in range(n - 1):
        res = a[i] - 2 * a[i + 1]
        if res < 0:
            return -1
        ans = max(ans, res)
    return ans


for _ in range(int(input())):
    print(solve())