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

using namespace std;

long long over3(long long n) {
    return n * (n - 1) * (n - 2) / 6;
}

long long over2(long long n) {
    return n * (n - 1) / 2;
}

bool enough(const vector<int> &matches, int playersCount) {
    int lower{};
    int higher = playersCount;
    // cerr << "    players count: " << playersCount << " - ";
    for (unsigned p = 0; p < matches.size() - 1; ++p) {
        int curr = 0;
        long long currMatches;
        do {
            ++curr;
            --higher;
            if (higher < 0) {
                // cerr << " - nok\n";
                return false;
            }
            currMatches = over3(curr) + (lower + higher) * over2(curr) + lower * (long long)curr * higher;
        } while (currMatches < matches[p]);
        // cerr << curr << ' ';
        lower += curr;
    }
    // cerr << higher << " ";
    bool res = over3(higher) + lower * over2(higher) >= matches.back();
    // cerr << (res ? " - ok" : " - nok") << endl;
    return res;
}

int binarySearch(const vector<int> &matches, int bad, int good) {
    while (bad < good - 1) {
        int middle = (bad + good) / 2;
        if (enough(matches, middle)) {
            good = middle;
        } else {
            bad = middle;
        }
    }
    return good;
}

void doOne() {
    int n;
    cin >> n;
    vector<int> matches;
    matches.resize(n);
    int k = 0;
    for (int i = 0; i < n; ++i) {
        cin >> matches[k];
        if (matches[k] > 0) {
            k++;
        }
    }
    matches.resize(k);
    if (k == 1) {
        int n = 2;
        long long res;
        do {
            res = over3(++n);
        } while (res < matches[0]);
        cout << n << "\n";
        return;
    }
    int playersCount = k + 2;
    if (enough(matches, playersCount)) {
        cout << playersCount << "\n";
        return;
    }
    do {
        playersCount <<= 1;
    } while (!enough(matches, playersCount));
    playersCount = binarySearch(matches, playersCount >> 1, playersCount);
    cout << playersCount << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        doOne();
    }
}