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
#include <iostream>
#include <vector>
using namespace std;

#define LL long long

class BigBajtTournament {
    static LL sum_j(LL u, LL v) {
        LL cnt = (v - u + 1);
        return (u + v) * cnt / 2;
    }

    static LL sum_j2(LL u, LL v) {
        auto f = [](LL x) -> LL {
            return x * (x + 1) * (2 * x + 1) / 6;
        };
        return f(v) - f(u - 1);
    }

    static LL F(LL L, LL x, LL P) {
        if (x <= 0) return 0;
        LL u = L + 1;
        LL v = L + x;
        LL cnt = x;
        LL s1 = sum_j(u, v) - cnt;
        LL s2 = sum_j2(u, v);
        LL sj = sum_j(u, v);
        return P * s1 - (s2 - sj);
    }

    static bool canAchieve(LL P, int n, const vector<LL> &a) {
        LL L = 0;
        for (int m = 0; m < n - 1; m++) {
            LL req = a[m];
            LL available = P - L;
            if (F(L, available, P) < req) return false;
            LL lo = 0, hi = available;
            while (lo < hi) {
                LL mid = (lo + hi) / 2;
                if (F(L, mid, P) >= req) hi = mid;
                else lo = mid + 1;
            }
            L += lo;
        }
        LL x_last = P - L;
        if (F(L, x_last, P) < a[n-1]) return false;
        return true;
    }

public:
    static void resolve() {

        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            vector<LL> a(n);
            LL totalGames = 0;
            for (int i = 0; i < n; i++) {
                cin >> a[i];
                totalGames += a[i];
            }

            LL lo = 3, hi = 3;
            while (!canAchieve(hi, n, a)) {
                hi *= 2;
                if (hi > 2000000) break;
            }

            LL ans = hi;
            while (lo <= hi) {
                LL mid = (lo + hi) / 2;
                if (canAchieve(mid, n, a)) {
                    ans = mid;
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }

            cout << ans << endl;
        }
    }
};

int main() {
    BigBajtTournament::resolve();
    return 0;
}