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
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int tesc;
	 cin >> tesc;
	vector<int> odp;
	while(tesc--)
        {
		int budy; cin >> budy;
		vector<long long> gry(budy);
		for (int ind = 0; ind < budy; ind++)
		{
			cin >> gry[ind];
		}
		long long sumG = 0;
		int ile = 0;
		for (int ind = 0; ind < budy; ind++)
        {
			sumG += gry[ind];
			if(gry[ind] > 0) ile++;
		}
		int dol = 3;
		dol = max(dol, ile);
		int tmp = dol;
		while((long long)tmp * (tmp - 1) * (tmp - 2) / 6 < sumG) tmp++;
		dol = tmp;
		int gor = dol;
		auto ok = [&](int tgr) -> bool
		{
			long long sump = 0;
			for (int ind = 0; ind < budy; ind++)
			{
				long long req = gry[ind];
				bool mid = (ind != 0 && ind != budy - 1);
				int minx = 0, maxx = tgr, ans = tgr + 1;
				while(minx <= maxx)
				{
					int miv = (minx + maxx) / 2;
					long long wyn = 0;
					if(miv < 2)
					{
						if(mid)
						{
							if(miv == 1)
                                {
								int dod = tgr - miv;
								int lew = dod / 2;
								int pra = dod - lew;
								wyn = 1LL * miv * lew * pra;
							}
							else wyn = 0;
						}
						else wyn = 0;
					}
					else
                        {
						long long c2 = 1LL * miv * (miv - 1) / 2;
						long long c3 = (miv >= 3) ? 1LL * miv * (miv - 1) * (miv - 2) / 6 : 0;
						long long part = c3 + c2 * (tgr - miv);
						wyn = part;
						if(mid)
						{
							int dod = tgr - miv;
							int lew = dod / 2;
							int pra = dod - lew;
							wyn += 1LL * miv * lew * pra;
						}
					}
					if(wyn >= req)
					{
						ans = miv;
						maxx = miv - 1;
					} else
					{
						minx = miv + 1;
					}
				}
				sump += ans;
				if(sump > tgr)
                    return false;
			}
			return sump <= tgr;
		};
		while(!ok(gor)) gor *= 2;
		int res = gor;
		while(dol <= gor)
            {
			int sro = (dol + gor) / 2;
			if(ok(sro))
			{
				res = sro;
				gor = sro - 1;
			} else
			{
				dol = sro + 1;
			}
		}
		odp.push_back(res);
	}
        for(auto val : odp)
            cout << val << endl;
	return 0;
}