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
#include <iostream>
#include <vector>

template<typename F>
int64_t bs(int64_t target, int64_t l, int64_t r, F f) {
    int64_t distance = r - l;
    // while (l < r) {
    while (distance > 0) {
        // int64_t mid = (l + r)/2;
        int64_t step = distance/2;
        int64_t mid = l + step;
        int64_t fmid = f(mid);
        if (fmid < target) {
            l = mid + 1;
            distance -= step + 1;
        } else {
            // r = mid - 1;
            distance = step;
        }
    }
    return l;
}

int main() {
    int t;
    std::cin >> t;

    for (int test = 0; test < t; ++test) {
        int n;
        std::cin >> n;

        std::vector<int> a(n, 0);
        for (int i = 0; i < n; ++i) {
            int ai;
            std::cin >> ai;
            a[i] = ai;
        }

        int64_t min = bs(true, 0, 1000010ll, [&a, n] (int64_t sum) {
            int64_t left = 0;
            for (int i = 0; i < n; ++i) {
                auto opts = [sum, left] (int64_t here) -> int64_t {
                    int64_t right = sum - left - here;
                    return left*here*right + here*(here - 1)*(sum - here)/2 + here*(here - 1)*(here - 2)/6;
                };
                // int64_t here = bs(a[i], 0, sum - left + 1, opts);
                int64_t here = bs(a[i], 0, sum - left, opts);
                if (opts(here) < a[i]) {
                    return false;
                }

                left += here;
                if (left > sum) {
                    return false;
                }
            }
            return left <= sum;
        });
        std::cout << min << std::endl;
    }
    return 0;
}