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
#include <bits/stdc++.h>

using namespace std;

int n;
int tournaments[200001];

int choose2(int s)
{
    return s * (s - 1) / 2;
}
int choose3(int s)
{
    return s * (s - 1) * (s - 2) / 6;
}

bool check(int s)
{
    int left = 0;
    for (int i = 1; i <= n; ++i)
    {
        int minimal = 0;
        for (int count = 0; count < 200; ++count)
        {
            long long right = s - left - count;
            if (right < 0) return false;
            if (left * right * count + choose2(count) * (left + right) + choose3(count) >= tournaments[i])
            {
                minimal = count;
                break;
            }
        }
        left += minimal;
    }
    return true;
}

void solve()
{
    cin >> n;

    for (int i = 1; i <= n; ++i) cin >> tournaments[i];

    int l = 1, r = 200000 * 200;

    while (l < r)
    {
        int m = (l + r) / 2;

        if (check(m))
            r = m;
        else
            l = m + 1;
    }

    cout << r << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;

    for (int i = 0; i < t; ++i)
        solve();
}