1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
def licz_trojki(x):
    if x < 3:
        return 0
    return x * (x - 1) * (x - 2) // 6

def minimalna_liczba_graczy(suma_rozgrywek):
    k = 3
    while licz_trojki(k) < suma_rozgrywek:
        k += 1
    return k

def minimalni_gracze_skrajny(rozgrywki_skrajne, liczba_budynkow):
    if rozgrywki_skrajne <= 0:
        return 1
    m = 2
    while True:
        F = licz_trojki(m) + (m * (m - 1) // 2) * (liczba_budynkow - 1)
        if F >= rozgrywki_skrajne:
            return m
        m += 1

def zaokraglij_w_gore(x):
    xi = int(x)
    return xi + 1 if x > xi else xi

liczba_testow = int(input())
przypadki_testowe = []
for _ in range(liczba_testow):
    n = int(input())
    rozgrywki_budynki = list(map(int, input().split()))
    przypadki_testowe.append((n, rozgrywki_budynki))

wyniki = []
for (n, rozgrywki_budynki) in przypadki_testowe:
    if n == 1:
        wynik = minimalna_liczba_graczy(rozgrywki_budynki[0])
    else:
        suma_rozgrywek = sum(rozgrywki_budynki)
        k_global = minimalna_liczba_graczy(suma_rozgrywek)
        gracze_budynku1 = minimalni_gracze_skrajny(rozgrywki_budynki[0], n)
        gracze_budynku_n = minimalni_gracze_skrajny(rozgrywki_budynki[-1], n)
        k_skrajny = gracze_budynku1 + gracze_budynku_n + (n - 2)
        if rozgrywki_budynki[0] == 0 and rozgrywki_budynki[-1] == 0:
            k_skrajny = n
        if n > 2:
            max_rozgrywki_wewnetrzne = max(rozgrywki_budynki[1:-1])
            if max_rozgrywki_wewnetrzne > 0:
                k_wewnetrzny = 1 + zaokraglij_w_gore(2 * (max_rozgrywki_wewnetrzne ** 0.5))
            else:
                k_wewnetrzny = n
        else:
            k_wewnetrzny = 0
        wynik = max(k_global, k_skrajny, k_wewnetrzny, n)
    wyniki.append(wynik)

for wynik in wyniki:
    print(wynik)