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
#include <bits/stdc++.h>
using namespace std;

void test_case() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int& x : a) {
		cin >> x;
	}
	int low = 0, high = 1e6 + 1000;
	while (low < high) {
		int mid = (low + high) / 2;
		int used = 0, remaining = mid;
		bool ok = true;
		for (int i = 0; i < n; i++) {
			int l = 0, h = remaining + 1;
			while (l < h) {
				int here = (l + h) / 2;
				long long tmp = (long long) used * here * (i == n - 1 ? 0 : remaining - here);
				tmp += (long long) here * (here - 1) / 2 * (used + (i == n - 1 ? 0 : remaining - here));
				tmp += (long long) here * (here - 1) * (here - 2) / 6;
				if (tmp >= a[i]) {
					h = here;
				}
				else {
					l = here + 1;
				}
			}
			if (l == remaining + 1) {
				ok = false;
				break;
			}
			used += l;
			remaining -= l;
		}
		if (ok) {
			high = mid;
		}
		else {
			low = mid + 1;
		}
	}
	cout << low << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		test_case();
	}
}