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

typedef long long ll;

int n;
ll M;

bool good(ll y, ll x, ll z) {
	return y * x * z + ((x * (x - 1ll)) / 2ll) * (y + z) + (x * (x - 1ll) * (x - 2ll)) / 6ll >= M;
}

ll l;

void upd(ll P, ll K, ll &x, ll c) {
	ll p = P, k = K;
	while(p <= k) {
		ll m = (p + k) / 2ll;
		if(good(l, m, c - m)) {
			if(x != -1) x = min(x, m);
			else x = m;
			k = m - 1ll;
		}
		else p = m + 1ll;
	}
}


	vector <ll> a;

bool check(ll c) {
	l = 0;
	for(int i = 0; i < n; ++i) {
		M = a[i];

		ll delta = (c - l + 1ll) * (c - l + 1ll) + 6ll * l * c - 3ll * (l + c);
		ll x11 = (c - l + 1ll - (ll) sqrt(delta)) / 3ll;
		ll x12 = (c - l + 1ll - (ll) (sqrt(delta) + 1)) / 3ll;
		ll x21 = (c - l + 1ll + (ll) sqrt(delta)) / 3ll;
		ll x22 = (c - l + 1ll + (ll) (sqrt(delta) + 1)) / 3ll;

		ll x = -1;
		upd(0, x11, x, c);
		upd(0, x12, x, c);
		upd(x11, x21, x, c);
		upd(x11, x22, x, c);
		upd(x12, x21, x, c);
		upd(x12, x22, x, c);
		upd(x21, c, x, c);
		upd(x22, c, x, c);

		if(x == -1) return 0;

		c -= x;
	}
	return 1;
}

void solve() {
	scanf("%d", &n);
	a.clear();
	a.resize(n);
	for(ll &x : a) scanf("%lld", &x);

	ll p = 0ll, k = 2000005ll, ans = -1ll; // chyba
	while(p <= k) {
		ll m = (p + k) / 2ll;
		if(check(m)) {
			ans = m;
			p = m + 1ll;
		}
		else k = m - 1ll;
	}

	assert(ans != -1ll);
	printf("%lld\n", ans);
}

int main() {
	int t; scanf("%d", &t);
	for(++t; --t;)
		solve();
	return 0;
}