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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>v;
ll n;
bool czek(ll k)
{
    //cout<<k<<endl;
    //k-=(n+2);
    ll pref=0, suf=k;
    vector<ll>cur;
    cur.push_back(2);
    for(int i=2; i<n; i++)
        cur.push_back(1);
    cur.push_back(2);
    for(int i=0; i<n; i++)
    {
        suf-=cur[i];
        //cout<<i<<" "<<cur[i]<<" "<<pref<<" "<<suf<<" "<<(pref+suf)*((cur[i]*(cur[i]-1))/2)<<" "<<cur[i]*pref*suf<<" "<<(((cur[i]*(cur[i]-1)*(cur[i]-2))/6))<<" "<<v[i]<<endl;
        if((pref+suf)*((cur[i]*(cur[i]-1))/2)+cur[i]*pref*suf+(((cur[i]*(cur[i]-1)*(cur[i]-2))/6))<v[i])
        {
            ll a=pref+suf, b=(pref*suf-pref-suf), c=-(2*v[i]);
            //cout<<a<<" "<<b<<" "<<c<<endl;
            ll delt=b*b-(4*a*c);
            if(delt<0)
                return 0;
            ll sqd=sqrt(delt);
            //if(sqd*sqd!=delt)
            //    sqd++;
            cur[i]=((-b+sqd)+(2*a-1))/(2*a);
            if(i==0||i==n-1)
                suf-=(cur[i]-2);
            else
                suf-=(cur[i]-1);
            //cout<<i<<" "<<cur[i]<<" "<<pref<<" "<<suf<<" "<<(pref+suf)*((cur[i]*(cur[i]-1))/2)<<" "<<cur[i]*pref*suf<<" "<<(((cur[i]*(cur[i]-1)*(cur[i]-2))/6))<<" "<<v[i]<<endl;
            while(suf>=0&&(pref+suf)*((cur[i]*(cur[i]-1))/2)+cur[i]*pref*suf+(((cur[i]*(cur[i]-1)*(cur[i]-2))/6))<v[i])
            {
                //cout<<(pref+suf)*((cur[i]*(cur[i]-1))/2)+cur[i]*pref*suf+(((cur[i]*(cur[i]-1)*(cur[i]-2))/6))<<" BB\n";
                cur[i]++;
                suf--;
            }
            //cout<<delt<<" "<<sqd<<" "<<cur[i]<<endl;
        }
        //cout<<cur[i]<<" AA\n";
        k-=cur[i];
        //cout<<k<<endl;
        pref+=cur[i];
        if(k<0)
            return 0;
    }
    return 1;

}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        v.clear();
        for(int i=0; i<n; i++)
        {
            ll cur;
            cin>>cur;
            if(cur)
                v.push_back(cur);
        }
        n=v.size();
        if(!n)
            cout<<0<<"\n";
        else if(n==1)
        {
            ll sum=v[0];
            ll ans=0;
            if(sum)
            {
                ans=3;
                while(ans*(ans-1)*(ans-2)<sum*6)
                    ans++;
            }
            cout<<ans<<"\n";
        }
        else
        {
            ll a=n+2, b=10000;
            while(a!=b)
            {
                ll mid=(a+b)/2;
                if(czek(mid))
                    b=mid;
                else
                    a=mid+1;
            }
            cout<<a<<"\n";

        }

    }
}