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
#include <cstdio>
#include <cstdint>
#include <vector>

bool possible(const std::vector<int>& T, int n, int cnt) {
	int next, S, l, r, m, i;
	int64_t L, stay;
	bool last_pos;
	L = 0;
	next = cnt;
	for (i = 0; i < n; ++i) {
		S = next;
		l = -1;
		r = S + 1;
		while (r - l > 1) {
			m = (l + r) / 2;
			last_pos = (m >= 1000) or (m * (6 * L * (S - m) + 3 * (L + S - m) * (m - 1) + (m - 1) * (m - 2)) / 6 >= T[i]);
			if (last_pos) {
				r = m;
			}
			else {
				l = m;
			}
		}
		stay = last_pos ? m : m + 1;
		if ((stay < 1000) && (stay * (6 * L * (S - stay) + 3 * (L + S - stay) * (stay - 1) + (stay - 1) * (stay - 2)) / 6 < T[i])) {
			return false;
		}
		next -= stay;
		L += stay;
	}
	return true;
}

void test_case() {
	int n, l, r, m, i, x;
	bool last_pos;
	std::vector<int> T;
	scanf("%d", &n);
	T.reserve(n + 8);
	for (i = 0; i < n; ++i) {
		scanf("%d", &x);
		T.push_back(x);
	}
	l = 0;
	r = 200000000;
	while (r - l > 1) {
		m = (l + r) / 2;
		last_pos = possible(T, n, m);
		if (last_pos) {
			r = m;
		}
		else {
			l = m;
		}
	}
	printf("%d\n", last_pos ? m : m + 1);
}

int main () {
	int t, i;
	scanf("%d", &t);
	for (i = 0; i < t; ++i) {
		test_case();
	}
	return 0;
}