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

void solve(){
    ll n;
    cin >> n;
    vector<ll> vec;
    for (ll i = 1,c; i<=n; i++){
        cin >> c;
        if (c)vec.push_back(c);
    }
    n=vec.size();
    ll l = n,p=183*n,x;
    while(l<p){
        x=(l+p)/2;
        ll sm=0;
        auto f = [&](ll k){return (x-k)*k*(k-1)/2+k*(k-1)*(k-2)/6+k*sm*(x-k-sm);};
        for (ll i = 0; sm<=x && i<n; i++){
            ll now=1;
            while(sm+now<=x && f(now)<vec[i])now++;
            sm+=now;
        }
        if (sm>x){
            l=x+1;
            continue;
        }
        p=x;
    }
    cout << l << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    while(t--)solve();
}