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
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define JOIN_(X, Y) X##Y
#define JOIN(X, Y) JOIN_(X, Y)
#define TMP JOIN(tmp, __LINE__)
#define PB push_back
#define SZ(x) int((x).size())
#define REP(i, n) for (int i = 0, TMP = (n); i < TMP; ++i)
#define FOR(i, a, b) for (int i = (a), TMP = (b); i <= TMP; ++i)
#define FORD(i, a, b) for (int i = (a), TMP = (b); i >= TMP; --i)

#ifdef DEBUG
#define DEB(x) (cerr << x)
#else
#define DEB(x)
#endif

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef unsigned int uint;

const int INF = 1e9 + 9;

template <typename S, typename T> ostream &operator<<(ostream &os, const pair<S, T> &p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "[";
    for (int i = 0; i < SZ(vec); ++i) {
        os << vec[i];
        if (i != SZ(vec) - 1) {
            os << ", ";
        }
    }
    os << "]";
    return os;
}

ll inline cnt(ll pos, ll players) { return pos * (players - pos - 1); }

bool check(vi t, int players) {
    int n = SZ(t);
    DEB("check players=" << players << " n=" << n << "\n");

    ll cnt_sum = 0;
    DEB("cnt:\n");
    // REP(i, players) {
    //     ll c = cnt(i, players);
    //     // DEB(c << ", ");
    //     cnt_sum += c;
    // }

    DEB("\n");
    DEB("cnt_sum=" << cnt_sum << "\n");

    int pos = 0;
    for (int &x : t) {
        while (pos < players) {
            if (x <= 0) {
                break;
            }
            ll take = min(static_cast<ll>(x), cnt(pos, players));
            x -= take;
            ++pos;
        }
        if (x > 0) {
            // if (players > 10000) {
            // DEB("left=" << t << "\n");
            // }
            return false;
        }
    }

    return true;
}

void inline one() {
    int n;
    cin >> n;
    vi t(n);
    REP(i, n) { cin >> t[i]; }
    // DEB("input t=" << t << "\n");
    int max_players = 1;
    while (not check(t, max_players)) {
        max_players *= 2;
    }
    int a = max_players / 2;
    int b = max_players;
    DEB("a=" << a << " b=" << b << "\n");
    while (a <= b) {
        int d = (a + b) / 2;
        DEB("  d=" << d << "\n");
        bool ok = check(t, d);
        DEB("    ok=" << ok << "\n");
        if (ok) {
            b = d - 1;
        } else {
            a = d + 1;
        }
    }
    cout << a << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int z;
    cin >> z;
    while (z--)
        one();
}