\(A\) の要素が全て \(0\) である場合の答えは \(0\) です。以降は \(0\) でない要素が存在する場合を考えます。

各操作によって \(A_i-2A_{i+1}\) の値は \(0\) または \(1\) 減少します。したがって、\(A_i-2A_{i+1}<0\) となる \(i\) が存在する場合答えは -1 で、さらに答えの下界として \(\displaystyle\max_i (A_i-2A_{i+1})\) が得られます。

さらに、 \(0\) でない要素が存在するので下界 \(\displaystyle\max\left(1,\max_i (A_i-2A_{i+1})\right)\) が分かります。

そして、この下界は実際に達成できます。

\(\displaystyle D_i=A_i-2A_{i+1},K=\max_i D_i\) とします。

\(K=0\) の場合、\(x_0=A_1\) とすることで \(A\) の要素を全て \(0\) にすることができるため答えは明らかに \(1\) です。以降は \(K\geq 1\) の場合を考えます。

\(X=(X_1,X_2,\ldots,X_K)\) を以下のように構成します：

• \(X=(0,0,\ldots,0)\) とする。
• \(i=1,2,\ldots,N-1\) の順に以下を行う：
  • \(X_1,X_2,\ldots,X_{D_i}\) にそれぞれ \(2^{i-1}\) を足す。
• \(X_1\) に \(A_N\) を足す。

このとき、\(i\) 回目に \(x_0=X_i\) を選ぶことで \(K\) 回で達成することができます。

実装例(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())