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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 big;
const int N=2e5+1;
int n;
ll a[N];
bool can(ll m){
	ll lhs=0;
	for(int i=1; i<=n ;i++){
		if(a[i]==0) continue;//b=0
		ll l=1,r=m-lhs+1;
		while(l!=r){
			ll b=(l+r)/2;
			//check if a[i] having b is enough
			ll rhs=m-lhs-b;
			ll ways=6*lhs*rhs+3*(b-1)*(lhs+rhs)+(b-1)*(b-2);
			if(ways>=(6*a[i]+b-1)/b) r=b;
			else l=b+1;
		}
		if(lhs+l>m) return false;
		lhs+=l;
	}
	return true;
	
}
void solve(){
	cin >> n;
	ll ans=0;
	for(int i=1; i<=n ;i++){
		cin >> a[i];
	}
	ll l=0,r=5e7;//if everyone has 200 then win
	while(l!=r){
		ll mid=(l+r)/2;
		if(can(mid)) r=mid;
		else l=mid+1;
	}
	cout << l << '\n';
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;
	while(t--) solve();
}