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


bool check(LL po, vector<LL> &v){
	bool ok = true;
	LL przed = 0;
	
	for(auto x : v){
		
		LL b = 0;
		LL e = po;
		LL tu = -1;
		while(b <= e){
			LL mid = b/2 + e/2 + (b%2 + e%2)/2;
			LL A = przed * mid * (po-mid);
			LL B = przed * mid * (mid-1) / 2;
			LL C = mid * (mid-1) / 2 * (po - mid);
			LL D = mid * (mid-1) * (mid-2) / 6;
			if(A + B + C + D >= x){
				tu = mid;
				e = mid-1;
			}else{
				b = mid+1;
			}
		}
		if(tu==-1)return false;
		przed += tu;
		po -= tu;
	}
	
	return ok;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt;
	cin>>tt;
	while(tt--) {
		LL n;
		cin>>n;
		vector<LL> v(n);
		for(auto &x : v)cin>>x;
		LL b = 0;
		LL e = 1000000LL;
		LL res = 10000000000LL;
		while(b <= e){
			LL mid = b/2 + e/2 + (b%2 + e%2)/2;
			if(check(mid, v)){
				res = min(res, mid);
				e = mid-1;
			}else{
				b = mid+1;
			}
		}
		cout<<res<<"\n";
	}
	return 0;
}