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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
int required[200001];
// long long po3[200];
// long long po2[1005];
int n;
// long long po(int a, int b)
// {
//     if(b==3 && a>102 || (b==2 && a>1002))
//         return 1e6;
//     if(b==3)
//         return po3[a];
//     if(b==2)
//         return po2[a];
//     return 0;

// }
// void initPo()
// {
//     po3[0]=po3[1]=po3[2]=0;
//     po3[3]=1;
//     for(long long i=4;i<=102;i++)
//     {
//         po3[i] = po3[i-1]*i/(i-3);
//     }
//     po2[0]=po2[1]=0;
//     po2[2]=1;
//     for(long long i=3;i<=1002;i++)
//     {
//         po2[i] = po2[i-1]*i/(i-2);
//     }
// }

long long formula(long long l, long long r, long long x)
{
    auto res = x*r*l+(l+r)*x*(x-1)/2+x*(x-1)*(x-2)/6;
    // cerr<<"formula "<<l<<" "<<r<<" "<<x<<" result: "<<res<<endl;
    return res;
}

int binSearchNumberOfWorkers(long long fullnumberOfWorkers, long long l, long long a, long long b, long long req, int rightindices)
{
    
    long long x = (a+b)/2;
    long long r = rightindices == 0 ? 0 : (fullnumberOfWorkers - l - x);
    
    // cerr<<"binsearching fullnumber of workers: "<<fullnumberOfWorkers<<" l: "<<l<<" r: "<<r<<" x: "<<x<<" a: "<<a<<" b: "<<b<<" req: "<<req<<" result: "<<formula(l,r,x)<<endl;
    if((b>a+1) && (l + x + rightindices + (rightindices > 0 ? 1 : 0)>fullnumberOfWorkers))
    {
        return binSearchNumberOfWorkers(fullnumberOfWorkers,l,a,x, req, rightindices);
        // cerr<<"fullnumber of workers: "<<fullnumberOfWorkers<<" l: "<<l<<" a: "<<a<<" b: "<<b<<" req: "<<req<<" result: "<<endl;
        // cerr<<"returned -1 with value "<<endl;
        // return -1;
    }
    else
    if((b<=a+1) && (l+b+ rightindices + (rightindices > 0 ? 1 : 0)>fullnumberOfWorkers))
    {
        // cerr<<"fullnumber of workers: "<<fullnumberOfWorkers<<" l: "<<l<<" a: "<<a<<" b: "<<b<<" req: "<<req<<" result: "<<endl;
        // cerr<<"returned -1 with value "<<endl;
        return -1;
    }
    if(b<=a+1)
    {
        // cerr<<"fullnumber of workers: "<<fullnumberOfWorkers<<" l: "<<l<<" a: "<<a<<" b: "<<b<<" req: "<<req<<" result: "<<(formula(l,fullnumberOfWorkers - l - b,b) >= req ? b : -1)<<endl;
        // cerr<<"returned "<<(formula(l,rightindices == 0 ? 0 : (fullnumberOfWorkers - l - b),b) >= req ? b : -1)<<" with value "<<(formula(l,rightindices == 0 ? 0 : (fullnumberOfWorkers - l - b),b))<<endl;
        return formula(l,rightindices == 0 ? 0 : (fullnumberOfWorkers - l - b),b) >= req ? b : -1;
    }
    if(formula(l,r,x) >= req)
    {
        return binSearchNumberOfWorkers(fullnumberOfWorkers,l,a,x, req, rightindices);
    }
    else
    {
        return binSearchNumberOfWorkers(fullnumberOfWorkers,l,x,b, req, rightindices);
    }
}

bool trySolve(int howMany)
{
    int l=0;
    int fullnumberOfWorkers = howMany;
    
    for(int i=0;i<n;i++)
    {
        
        int usedNumberofWorkers = binSearchNumberOfWorkers(fullnumberOfWorkers,l,0,fullnumberOfWorkers-l, required[i], n-i-1);
        if(usedNumberofWorkers==-1)
            return false;
        l += usedNumberofWorkers;

    }
    return true;
}

int binSearchSolution(int a, int b)
{
    // cerr<<"binsearching solution "<<a<<" "<<b<<" "<<(a+b)/2<<endl;
    if(b<=a+1)
        return b;
    if(trySolve((a+b)/2))
    {
        return binSearchSolution(a,(a+b)/2);
    }
    else
    {
        return binSearchSolution((a+b)/2,b);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    int t;
    // initPo();
    cin>>t;
    for(;t>0;t--)
    {
        cin>>n;
        int j=0;
        for(int i=0;i<n;i++)
        {
            cin>>required[j];
            if(required[j]>0)
                j++;
        }
        n=j;
        //if(n>1)
        {
            cout<<binSearchSolution(0,203000)<<endl;
            // cout<<binSearchNumberOfWorkers(200,0,2,200, required[0],0)<<endl;
        }
        //else cout<<binSearchNumberOfWorkers(200,0,3,200, required[0])<<endl;
    }
}