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
#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define fr(i,n) for(int i=0; i<(n); i++)
#define frx(i,a,b) for(int i=(a); i<=(b); i++)
#define ok(cond) cout << ((cond) ? "Yes" : "No") << "\n";
#define watch(x) cerr << (#x) << " == " << (x) << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef const int ci;
typedef const ll cll;
typedef const ld cld;
typedef pair<int,int> pii;
typedef set<int> si;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<int,ll>> vpill;


template<typename T1, typename T2>
istream& operator>>(istream& is, pair<T1,T2>& p) {
    return is >> p.st >> p.nd;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1,T2>& p) {
    return os << p.st << " " << p.nd;
}


template<typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    for (T x : v) {
        os << x << " ";
    }
    return os;
}

template<typename T>
ostream& operator<<(ostream& os, set<T>& s) {
    for (T x : s) {
        os << x << " ";
    }
    return os;
}

#define int ll 
const int MAX_BIN3 = 183;
const int N = 2e5;
int a[N+5];
int n;

ll get_max_matches(ll l, ll m, ll r) {
    return l * m * r +
           (l+r) * (m*(m-1LL) / 2LL) +
           m*(m-1LL)*(m-2LL) / 6LL;
}

int get_min_players_house(int total, int l_players, ll matches) {
    if (matches == 0) return 0;

    int r_players = total - l_players;
    int l = 1;
    int r = min(MAX_BIN3, total-l_players)+1;
    while (l < r) {
        int m = (l+r)/2;
        if (get_max_matches(l_players, m, r_players-m) < matches) {
            l = m+1;
        } else {
            r = m;
        }
    }
    return l;
}

bool check_if_possible(int total) {
    int left = 0;
    fr(i,n-1) {
        int players = get_min_players_house(total, left, a[i]);
        if (players > total-left) {
            return 0;
        }
        left += players;
    }
    if ((total-left <= MAX_BIN3) && get_max_matches(left, total-left, 0) < a[n-1]) {
        return 0;
    }
    return 1;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    fr(C, t) {
        cin >> n;
        fr(i,n) {
            cin >> a[i];
        }

        int l = 0, r = min(N+100, MAX_BIN3*n);
        while (l < r) {
            int m = (l+r)/2;
            if (!check_if_possible(m)) {
                l = m+1;
            } else {
                r = m;
            }
        }

        cout << l << "\n";       
    }

    return 0;
}