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

LL binom2(LL n)
{
	return n*(n-1) / 2;
}

LL binom3(LL n)
{
	return n*(n-1)*(n-2) / 6;
}

void solve()
{
	int n;
	cin >> n;
	vector<LL> A(n);
	for (auto &a : A)
		cin >> a;
	auto CHECK = [&](LL K){
		auto F = [&](LL p, LL x){
			return binom3(x) + binom2(x)*(K-x) + x*p*(K-p-x);
		};
		auto OK = [&](LL a, LL p, LL x){
			return F(p, x) >= a;
		};
		LL p = 0;
		for (auto &a : A)
		{
			LL poczatek = 0;
			LL koniec = K-p;
			while (poczatek < koniec)
			{
				LL srodek = (poczatek + koniec) / 2;
				if (OK(a, p, srodek))
					koniec = srodek;
				else
					poczatek = srodek+1;
			}
			LL x = poczatek;
			if (!OK(a, p, x))
				return 0;
			p += x;
		}
		return 1;
	};
	LL poczatek = 0;
	LL koniec = 1;
	while (!CHECK(koniec))
		koniec *= 2;
	while (poczatek < koniec)
	{
		LL srodek = (poczatek + koniec) / 2;
		if (CHECK(srodek))
			koniec = srodek;
		else
			poczatek = srodek+1;
	}
	cout << poczatek << "\n";
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);

	int t;
	cin >> t;
	while (t--)
		solve();
}