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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int a[1<<18];
signed main()
{
	for(int T=read();T--;)
	{
		int n=read(),l=0,r=1e9,ans=r+1;
		for(int i=1; i<=n; ++i) a[i]=read();
		while(l<=r)
		{
			int mid=(l+r)>>1,x=0;
			for(int i=1; i<=n&&x<=mid; ++i)
			{
				int wl=0,wr=min(10000,mid-x),ww=mid-x+1;
				while(wl<=wr)
				{
					int mm=(wl+wr)>>1;
					ll W=1ll*mm*(mm-1)*(mm-2)/6
					+1ll*mm*(mm-1)/2*(mid-mm)
					+1ll*mm*x*(mid-mm-x);
					if(W<a[i]) wl=mm+1;
					else ww=mm,wr=mm-1;
				}
				x+=ww;
			}
			if(x<=mid) ans=mid,r=mid-1;
			else l=mid+1;
		}
		printf("%d\n",ans);
	}
	return 0;
}