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

ll F(ll w, ll x, ll t) {
    ll wynik = 0;
    if(x >= 3) {
        wynik = (x * (x - 1) * (x - 2)) / 6;
        return wynik + (x * w * (t - w - x)) + (((x * (x - 1)) / 2) * (t - x));
    }
    if(x >= 2) {
        wynik = ((x * (x - 1)) / 2) * (t - x);
        return wynik + (x * w * (t - w - x));
    }
    return x * w * (t - w - x);
}

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

    int t; 
    cin >> t;
    while(t--){
        int n; 
        cin >> n;
        vector<ll> a(n);
        ll suma = 0;
        for(int i = 0; i < n; i++){
            cin >> a[i];
            suma += a[i];
        }
        
        ll Start = 3;
        ll End = 2000007;
        ll wynik = End;
        while(Start <= End){
            ll Mid = (Start + End) / 2;
            if((Mid * (Mid - 1) * (Mid - 2)) / 6 < suma){
                Start = Mid + 1;
                continue;
            }
            ll ile = 0;
            bool czy = true;
            for(int i = 0; i < n; i++){
                ll start = 0;
                ll end = Mid - ile;
                ll need = -1;
                while(start <= end){
                    ll mid = (start + end) / 2;
                    if(F(ile, mid, Mid) >= a[i]){
                        need = mid;
                        end = mid - 1;
                    } 
                    else start = mid + 1;
                }
                if(need == -1){
                    czy = false;
                    break;
                }
                ile += need;
                if(ile > Mid){
                    czy = false;
                    break;
                }
            }
            if(czy){
                wynik = Mid;
                End = Mid - 1;
            }
            else Start = Mid + 1;
        }
        cout << wynik << endl;
    }
}