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

#ifdef DEBUG
auto &operator<<(auto &o, pair<auto, auto> p) {
    return o << "(" << p.first << ", " << p.second <<")";
}
auto operator<<(auto &o, auto x)-> decltype(x.end(), o) {
    o << "{";int i = 0;
    for(auto e : x) o << ", "+!i++<<e;
    return o <<"}";
}
#define debug(x...) cerr << "["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x)
#else
#define debug(...) {}
#endif

#define int long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define fi first
#define se second
typedef pair <int, int> pii;

int choose3(int a) {
    return ((a-1) * (a-2) * a)/6ll;
}

int choose2(int a) {
    return ((a-1) * a)/2ll;
}

int f(int b, int ss, int p) {
    return choose3(b) + choose2(b) * (ss-b) + b * (ss - b - p) * p;
}


bool check(vector <int> &A, int ile) {
    debug(ile);
    int pref = 0;
    // vector <int> ret;
    for (int i=0; i<sz(A); ++i) {
        int rem = ile - pref;
        bool ok = false;
        int m=0, pp=0;
        
        for (int j=(i==sz(A)-1 ? min(190ll, rem) : 0); j<=min(190ll,rem); ++j) {
            debug(j);
            if (f(j, ile, pref) >= A[i]) {
                m = j;
                ok = true;
                break;
            }
        }

        if (i > 0) {
            for (int j=(i==sz(A)-1 ? m : 0); j<=m; ++j) {
                for (int p=1; p<=j; ++p) {
                    int ja = j - p; 
                    if (f(ja, ile, pref+p) >= A[i]) {
                        m = j;
                        pp = p;
                        ok = true;
                        j = 1e9;
                        break;
                    }
                }
            }
            // ret.back() += pp;
        }

        // ret.push_back(m - pp);
        // debug(i, ret);
        
        pref += m;

        if (!ok) {
            return false;
        }
    }
    // debug(ret);
    return true;
}


void test() {
    debug("TC______________________");
    int n; cin>>n;
    int ss = 0;
    vector <int> a(n);
    for (int i=0; i<n; ++i) {
        cin>>a[i];
        ss += a[i];
    }
    debug(a);
    
    int p = 1, k = 5e8+1, s, res=0;
    while (p <= k) {
        s = (p+k)/2;

        if (check(a, s)) {
            res = s;
            k = s-1;
        }
        else {
            p = s+1;
        }
    }

    cout<<res<<'\n';
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int t = 1; cin>>t;
  while (t--) {
    test();
  }
}