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

using namespace std;

bool checkQuery(vector<long long> *houses, long long query) {
    long long left = 0;
    for (long long i = 0; i < houses->size(); i++) {
        if (houses->at(i) > 0) {
            bool goNext = false;
            for (long long players = 1; players <= (query - left); players++) {
                long long tournaments = players * left * (query - players - left)
                    + players * (players - 1) * (query - players) / 2
                    + players * (players - 1) * (players - 2) / 6;
                if (tournaments < houses->at(i)) {
                    continue;
                } else {
                    left += players;
                    goNext = true;
                    break;
                }
            }
            if (!goNext) {
                return false;
            }
        }
    }
    return true;
}

void compute(vector<long long> *houses) {
    bool maxLimit = false;
    long long query = 10;
    long long negative = 0;
    long long positive = LLONG_MAX;
    while (negative + 1 < positive) {
        if (checkQuery(houses, query)) {
            positive = query;
            query = (positive + negative) / 2;
        } else {
            negative = query;
            if (positive == LLONG_MAX) {
                query = 2 * query;
            } else {
                query = (positive + negative) / 2;
            }
        }
    }
    cout << positive << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long t;
    cin >> t;

    for (long long i = 0; i < t; i++) {
        long long n;
        cin >> n;
        vector<long long> houses(n);
        for (long long j = 0; j < n; j++) {
            cin >> houses[j];
        }
        compute(&houses);
    }


}