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
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>


using namespace std;

const long long MAX_PL_IN_HOUSE = 183;

int nchoose3(int n) {
	return n * (n-1) * (n-2) / 6;
}

long long f(long long k, long long B, long long M, bool isFirst, bool isLast) {
	long long onlyB = nchoose3(B);
	long long twoFromB = (!isFirst || !isLast) ? (B * (B-1) * (M-B) / 2) : 0;
	long long oneFromB = (!isFirst && !isLast) ? k * (M-k-B) * B : 0;
	return onlyB + twoFromB + oneFromB;
}

long long minB(long long k, long long M, long long ai, bool isFirst, bool isLast) {
	long long B = 0;
	long long result = f(k, B, M, isFirst, isLast);
	while (result < ai) {
		B++;
		result = f(k, B, M, isFirst, isLast);
	}
	return B;
}

long long minBplusK(long long k, long long B, long long M, long long ai, bool isFirst, bool isLast) {
	long long kB = k + B;
	k++;
	B -= 2;
	
	while (k < kB) {
		while (f(k, B, M, isFirst, isLast) >= ai) {
			if (k + B < kB) {
				kB = k+B;
			}
			
			B--;
		}
		k++;
	}
	return kB;
}

long long minNextK(long long k, long long M, long long ai, bool isFirst, bool isLast) {
	int B = minB(k, M, ai, isFirst, isLast);
	if (isFirst) {
		return B;
	}
	return minBplusK(k, B, M, ai, isFirst, isLast);
}

bool isPossible(vector<long long>& games, long long M) {
	int minK = 0;
	
	for (int i = 0; i < games.size(); i++) {
		if (games[i] > 0 && minK >= M) {
			return false;
		}
		
		minK = minNextK(minK, M, games[i], i == 0, i == games.size() - 1);
	}
	
	return minK <= M;
}

long long binarySearchM(vector<long long>& games, long long minM, long long maxM) {
	if (minM + 1 == maxM) {
		return maxM;
	}
	
	long long mid = (minM + maxM + 1) / 2;

	bool poss = isPossible(games, mid);
		
	if (poss) {
		return binarySearchM(games, minM, mid);
	} else {
		return binarySearchM(games, mid, maxM);
	}
}

long long binarySearchStart(vector<long long>& games, long long start) {
	if (isPossible(games, start)) {
		return binarySearchM(games, 0, start);
	} else {
		return binarySearchStart(games, 8 * start);
	}
}

long long singleTest() {
	int n;
	cin >> n;
	
	vector<long long> games(n);
	
	
	
	for (int i = 0; i < n; i++) {
		long long x;
		cin >> x;
		games[i] = x;
	}
	
	return binarySearchStart(games, n + MAX_PL_IN_HOUSE);
}

int main() {
	
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	int t;
	cin >> t;
	vector<long long> results(t);
	
	for (int i = 0; i < t; i++) {
		long long result = singleTest();
		results[i] = result;
	}
	
	
	for (int i = 0; i < t; i++) {
		cout << results[i] << "\n";
	}
}