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

const int K = 191;
const int MAXN = 2e5 + 7; // TODO: 2e5 + 7

const int S = 2e3 + 7;
int dp[MAXN + S], tmp[MAXN + S];

const int INF = 1e9 + 7;

void solve_case() {
	int n; cin >> n;
	vector<int> arr(n + 1);
	for (int i = 1; i <= n; ++i) cin >> arr[i];
	for (int j = 0; j < n + S; ++j) dp[j] = tmp[j] = INF;
	tmp[0] = 0;
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		int l = 1, r = K, mid = 0;
		while (l < r) {
			mid = (l + r) / 2;
			if (mid * (mid - 1) * (mid - 2) >= arr[i] * 6) r = mid;
			else l = mid + 1;
		}
		int maxk = min(K, max(3, l) + 5);
		cnt += (arr[i] > 1);
		for (int j = max(0, cnt - 1); j < cnt + S; ++j) dp[j] = INF;
		for (int j = max(0, cnt - 1); j < cnt + S; ++j) {
			if (tmp[j] > n - i + S) continue;
			for (int k = 0; k < maxk; ++k) {
				if (j + k >= cnt + S) break;
				int case3 = k * (k - 1) * (k - 2) / 6;
				int case2 = (k * (k - 1) / 2) * j;
				int rem = arr[i] - case3 - case2;
				int extra = 0;
				if (rem > 0) {
					if (!k || (!j && k == 1)) continue;
					extra = (rem - 1) / (k * (k - 1) / 2 + k * j) + 1;
				}
				dp[j + k] = min(dp[j + k], max(tmp[j] - k, extra));
				if (rem < 0) break;
			}
		}
		for (int j = max(0, cnt - 1); j < cnt + S; ++j) tmp[j] = dp[j];
	}
	int ans = INF;
	for (int i = 0; i < n + S; ++i) {
		ans = min(ans, dp[i] + i);
	}
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) solve_case();
}