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
#include <bits/stdc++.h>
using namespace std;
unsigned long long int ile(int a1, int b1, int c1)
{
	unsigned long long int a=a1,b=b1,c=c1;
	unsigned long long int x;
	x=a*(a-1);
	x/=2;
	x*=(a-2);
	x/=3;
	unsigned long long int y=(a-1)*a;
	y/=2;
	y*=(b-a);
	unsigned long long int z=a*c*(b-a-c);
	return x+y+z;
}
void solve()
{
	int n;
	cin>>n;
	vector<unsigned long long int>v(n);
	for(int i=0; i<n; i++)
		cin>>v[i];
	//n=200000;
	//v.resize(n);
	//for(int i=0; i<n; i++)
	//	v[i]=1000000;
	int p=1;
	int k=202007;
	while(p<k)
	{
		int s=(p+k)/2;
		int ilsf=0;
		unsigned long long int mx=0;
		for(int i=0; i<n; i++)
		{
			int sus=0;
			while(ilsf+sus<=s&&ile(sus,s,ilsf)<v[i])
			{
				/*if(sus!=0)
					cout<<i<<" "<<s<<" "<<ilsf<<" "<<ile(sus,s,ilsf)<<"\n";*/
				sus++;
			}
			/*if(i<10)
				cout<<sus<<" ";
			if(i>n-10)
				cout<<sus<<" ";*/
			ilsf+=sus;
			if(ilsf>s)
				break;
		}
		//cout<<"\n\n"<<mx<<"\n";
		if(ilsf>s)
			p=s+1;
		else
			k=s;
	}
	cout<<p<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin>>t;
	while(t--)
		solve();
}