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

using namespace std;

typedef long long ll;


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

    const int A = 183;
    const int SMAX = 4*1e7;

    int t;
    cin >> t;

    int res[t + 1];

    for (int i = 1; i <= t; i++) {
        int n;
        cin >> n;

        int a[n + 1];
        for (int j = 1; j <= n; j++) {
            cin >> a[j];
        }

        int S_beg = 1;
        int S_end = SMAX;
        while (S_beg < S_end) {
            int S = (S_beg + S_end) / 2;
            bool attainable = true;
            ll l[n + 1];
            int s[n + 1];
            s[n] = 0;
            for (int j = n; j >= 1 && attainable; j--) {
                if (a[j] == 0) {
                    l[j] = 0;
                }
                else {
                    int beg = 1;
                    int end = min(A, S - s[j]);
                    while (beg < end) {
                        ll x = (beg + end) / 2;
                        if (a[j] <= x*(x-1)*(x-2)/6 + x*(x-1)/2*(S-x) + x*(S-x-s[j])*s[j]) {
                            end = x;
                        }
                        else {
                            beg = x + 1;
                        }
                    }
                    l[j] = end;
                    if (a[j] > l[j]*(l[j]-1)*(l[j]-2)/6 + l[j]*(l[j]-1)/2*(S-l[j]) + l[j]*(S-l[j]-s[j])*s[j]) {
                        attainable = false;
                    }
                }
                s[j - 1] = s[j] + l[j];
            }

            if (attainable) {
                S_end = S;
            }
            else {
                S_beg = S + 1;
            }
        }

        res[i] = S_end;
    }

    for (int i = 1; i <= t; i++) {
        cout << res[i] << "\n";
    }

    return 0;
}