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

long long k2(long long x) {
    if (x >= 2) return (x * (x - 1) / 2);
    return 0;
}

long long k3(long long x) {
    if (x >= 3) return x * (x - 1) * (x - 2) / 6;
    return 0;
}

long long brz(long long x, long long tgr) {
    return k3(x) + k2(x) * (tgr - x);
}

long long wew(long long x, long long lew, long long tgr) {
    long long pra = tgr - lew - x;
    if (pra < 0) return -1;
    return k3(x) + k2(x) * (lew + pra) + (long long)x * lew * pra;
}

long long ost(long long x, long long lew) {
    return k3(x) + k2(x) * lew;
}

template<typename F>//guwno zeby dzialalo
long long mnx(long long wym, long long l, long long r, F f) {
    long long wyn = -1;
    while (l <= r) {
        //cout << l << ' ' << r << '\n';
        long long mid = l + (r - l) / 2;
        if (f(mid) >= wym) {
            wyn = mid;
            r = mid - 1;
        } 
        else l = mid + 1;
    }
    return wyn;
}

bool moz(long long tgr, const vector<long long>& gry) {
    long long nbd = gry.size();
    if (tgr < 3) return 0;
    long long ogr = k3(tgr);
    for (auto ag : gry) if (ag > ogr) return 0;

    if (nbd == 1) return k3(tgr) >= gry[0];

    long long uzy = 0;
    long long req = 0;
    if (gry[0] > 0) {
        req = mnx(gry[0], 0, tgr, [tgr](long long xgr) { return brz(xgr, tgr); });
        if (req == -1) return 0;
    }
    uzy += req;

    for (long long ind = 1; ind < nbd - 1; ind++) {
        long long lew = uzy;
        long long xmn = mnx(gry[ind], 0, tgr - uzy, [lew, tgr](long long xgr) { return wew(xgr, lew, tgr); });
        if (xmn == -1) return 0;
        uzy += xmn;
        if (uzy > tgr) return 0;
    }

    long long lew = uzy;
    long long xmn = 0;
    if (gry[nbd - 1] > 0) {
        xmn = mnx(gry[nbd - 1], 0, tgr - uzy, [lew](long long xgr) { return ost(xgr, lew); });
        if (xmn == -1) return 0;
    }
    uzy += xmn;
    return uzy <= tgr;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    long long t;
    cin >> t;
    while (t--) {
        long long nbd;
        cin >> nbd;
        vector<long long> gry(nbd);
        long long sgr = 0;
        long long naj = 0;
        for (long long ind = 0; ind < nbd; ind++) {
            cin >> gry[ind];
            sgr += gry[ind];
            naj = max(naj, gry[ind]);
        }

        long long l = 3, r = max(3, 100);

        while (!moz(r, gry)) {
            r *= 2;
            if (r > 1000000) break;
        }

        long long wyn = r;
        while (l <= r) {
            //cout << l << ' ' << r << '\n';
            long long mid = l + (r - l) / 2;
            if (moz(mid, gry)) {
                wyn = mid;
                r = mid - 1;
            } 
            else l = mid + 1;
        }

        cout << wyn << "\n";
    }
}