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
//PROBLEM 4C
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mul(ll A, ll B) {
    A = min(A, 1ll<<30);
    B = min(B, 1ll<<30);
    return min(1ll<<30, A*B);
}
ll solve(vector<ll> a) {
    auto check = [&](ll S) {
        auto get_cnt = [&](ll L, ll X) {
            ll R = S - X - L;
            ll res = 0;
            res += mul(R, mul(X, L));
            res += mul(L + R, mul(X, X - 1)) / 2;
            res += mul(X, mul(X - 1, X - 2)) / 6;
            return res; 
        };
        ll L = 0;
        for(auto i : a) {
            ll X = -1;
            for(ll z = 1ll<<30; z>>=1;)
                if(L + X + z <= S && get_cnt(L, X + z) < i)
                    X += z;
            X++;
            if(L + X > S) return false;
            L += X;
        }
        return true;
    };
    ll S = 0;
    for(ll z = 1ll<<30; z>>=1;) {
        S += z*!check(S+z);
    }
    return S + 1;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<ll> a(n);
        for(auto &i : a) cin >> i;
        cout << solve(a) << '\n';
    }
}

/*
given that sum is S
putting minimum number of guys here won't hurt
*/