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
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
import math
from sys import stdin, stdout


# old_print = ""
def print_state():
    global old_print
    to_print = f"test {_}\n"
    to_print += f"{a=}\n"
    to_print += f"{missing=}\n"
    to_print += f"{max_missing=}\n"
    for i in missing:
        to_print += f"  {i} misses {get_missing_value(i)}\n"
    to_print += f"{interval_tree=}\n"
    print(to_print)
    if to_print == old_print:
        raise ValueError("looping detected")
    old_print = to_print

def n_po_3(k):
    return k * (k-1) * (k-2) // 6


def n_po_2(k):
    return k * (k-1) // 2


def brute_for_1(k):
    out = math.floor((k*6) ** (1/3)) + 1
    while n_po_3(out) < k:
        out += 1
    return out


def init_tree():
    start = n_size_base_2
    interval_tree[start] = 2
    for i in range(1, n-1):
        interval_tree[start + i] = 1
        i += 1
    interval_tree[start + n - 1] = 2
    for i in range(n_size_base_2-1, 0, -1):
        interval_tree[i] = interval_tree[2*i] + interval_tree[2*i+1]


def update_tree(i, delta):
    i += n_size_base_2
    interval_tree[i] += delta
    while i > 1:
        i >>= 1
        interval_tree[i] = interval_tree[2*i] + interval_tree[2*i+1]


def get_interval_sum(start, end):
    # print(f"getting {start=}, {end=}")
    start += n_size_base_2
    end += n_size_base_2
    out = 0
    while start < end:
        # print(f"in loop with {start=}, {end=}")
        if start % 2 == 1:
            out += interval_tree[start]
            start += 1
        if end % 2 == 1:
            end -= 1
            out += interval_tree[end]
        start >>= 1
        end >>= 1
    return out


def get_no_matches(i):
    no_before = get_interval_sum(0, i)
    no_after = get_interval_sum(i+1, n)
    no_inside = interval_tree[n_size_base_2 + i]
    out = 0
    out += n_po_3(no_inside)
    out += n_po_2(no_inside) * (no_before + no_after)
    out += no_before * no_inside * no_after
    # print(f"got no matches for {i}: {out}\n")
    return out


def get_missing_value(i):
    out = a[i] - get_no_matches(i)
    # print(f"got no missing for {i}: {out}\n")
    return out


def get_init_missing():
    MAX = max(a)
    ROOT_MAX = math.ceil(MAX ** (1/2))
    if n <= 2 * ROOT_MAX:
        return set(range(n))
    out = set({0, n-1})
    i = 1
    while (i+1) * (n-i) < MAX:
        out.add(i)
    i = n - 2
    while (i+1) * (n-i) < MAX:
        out.add(i)
    return out


def update_missing():
    to_remove = []
    for i in missing:
        val = get_no_matches(i)
        if val >= a[i]:
            to_remove.append(i)
    for i in to_remove:
        missing.remove(i)


t = int(stdin.readline())
for _ in range(t):
    n = int(stdin.readline())
    a = [int(x) for x in stdin.readline().split()]
    a = [x for x in a if x > 0]
    n = len(a)

    if n == 1:
        result = brute_for_1(a[0])
        stdout.write(str(result) + "\n")
        continue

    n_size_base_2 = 2 ** math.ceil(math.log2(n))
    interval_tree = [0] * (2 * n_size_base_2)

    init_tree()
    # print(f"{interval_tree=}\n")
    missing = get_init_missing()
    # print(f"init {missing=}\n")
    update_missing()
    # print(f"{missing=}\n")
    result = n + 2
    while len(missing) > 0:
        max_missing = max(missing, key = get_missing_value)
        # print_state()
        update_tree(max_missing, 1)
        update_missing()
        result += 1

    stdout.write(str(result) + "\n")