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
#include <iostream>
const int MAX_N = 200002;
long a_i[MAX_N];
int n;

long long count(long long L, long long S, long long P) {
	return L * S*P + S * (S - 1)*(L + P) / 2 + S * (S - 1)*(S - 2) / 6;
}

bool is_possible(int k) {
	long long L = 0;
	long long S = k;
	for (int i = 0; i < n; i++) {
		if (a_i[i] == 0) { 
			//std::cout << "0 "; 
			continue; 
		}
		if (count(L, S, 0) < a_i[i]) { 
			//std::cout << "WRONG (" << L <<", " << S << ")";
			return false; 
		}
		int a = 0;
		int b = S;
		while (a + 1 < b) {
			int mid = (a + b) / 2;
			if (count(L, mid, S - mid) >= a_i[i]) b = mid;
			else a = mid;
		}
		//std::cout << b << "->cout(" << L <<", " << b << ", " << S - b <<")="  << count(L,S-b,b) << "  ";
		L += b;
		S -= b;
	}
	//std::cout << " | ";
	return true;
}

int main()
{
	int t = 0;
	std::cin >> t;
	for (int testy = 0; testy < t; testy++) {
		std::cin >> n;
		for (int i = 0; i < n; i++) {
			int k = 0;
			std::cin >> k;
			a_i[i] = k;
		}
		int a = 0;
		int b = 1300000;
		//std::cout << "\n";
		while (a + 1 < b) {
			int mid = (a + b) / 2;
			if (is_possible(mid)) { 
				b = mid; 
				//std::cout << mid << " is possible\n"; 
			}
			else { 
				a = mid; 
				//std::cout << mid << " is impossible \n"; 
			}
		}
		std::cout << b << "\n";
		//std::cout << "ANS: " << b << "\n";
	}
}