## https://yukicoder.me/problems/no/3165 def solve2(N, A, X): f_index = 0 first = True for a in A: index = f_index if first: x = X // 2 + (1 if X % 2 == 1 else 0) x -= f_index // 2 a0 = min(a, x) index += 2 * a0 if index >= X: index = 1 first = False a -= a0 if f_index <= 2: f_index = index continue a0 = min(a, (f_index - 3) // 2 + 1) index += 2 * a0 if index >= X: break f_index = index continue else: f_index = index else: index += 2 * a if index >= X: break f_index = index continue return index >= X def solve(N, A): total_a = sum(A) A.sort(reverse=True) low = 0 high = total_a while high - low > 1: mid = (high + low) // 2 if solve2(N, A, mid): low = mid else: high = mid if solve2(N, A, high): return high else: return low def main(): T = int(input()) answers = [] for _ in range(T): N = int(input()) A = list(map(int, input().split())) ans = solve(N, A) answers.append(ans) for ans in answers: print(ans) if __name__ == "__main__": main()