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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2e5;

int t, n, tab[N+2], l, r, mid, l1, r1, mid1, used;

bool is_enough(ll x, ll y, ll z, int needed) {
    ll cnt = 0;
    cnt += x * y * z;
    if (y >= 2) {
        cnt += x * y * (y - 1) / 2;
        cnt += y * (y - 1) * z / 2;
    }
    if (y >= 3) cnt += y * (y - 1) * (y - 2) / 6;
    if (cnt >= needed) return true;
    return false;
}

bool check_possible() {
    for (int j = 1 ; j <= n ; j++) {
        l1 = 0;
        r1 = mid - used;
        while(l1 < r1) {
            mid1 = (l1 + r1) / 2;
            if(is_enough(used, mid1, mid - mid1 - used, tab[j])) r1 = mid1;
            else l1 = mid1 + 1;
        }
        if(!is_enough(used, l1, mid - l1 - used, tab[j])) return false;
        used += l1;
    }
    return true;
}

int main() {
    cin>>t;
    for(int i = 1 ; i<=t ; i++) {
        cin>>n;
        l = 0;
        for(int j = 1 ; j <= n ; j++) {
            cin>>tab[j];
            if(tab[j] > 0) l++;
        }
        r = l + 4000;
        while(l < r) {
            mid = (l + r) / 2;
            used = 0;
            if(check_possible()) r = mid;
            else l = mid + 1;
        }
        cout<<l<<"\n";
    }
}