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
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i < b;++i)
#define pb push_back
#define int long long
using namespace std;
void solve(){
    int n;
    cin>>n;
    vector<int> V,pref,num;
    FOR(i,0,n){
        int x;
        cin>>x;
        if(x > 0){
            V.pb(x);
        }
    }
    if(V.size() == 1){
        FOR(i,3,200){
            if(((i * (i - 1) * (i - 2)) / 6) >= V[0]){
                cout<<i;
                break;
            }
        }
        return ;
    }
    pref.pb(0);
    FOR(i,0,V.size()){
        int wart = pref[pref.size() - 1];
        if(i == 0 || i == (V.size() - 1)){
            pref.pb(wart + 2);
        }else{
            pref.pb(wart + 1);
        }
    }
    if(V.size() >= 3005){
        FOR(i,0,1001){
            num.pb(i);
        }
        FOR(i,V.size() - 1005,V.size()){
            num.pb(i);
        }
    }else{
        FOR(i,0,V.size()){
            num.pb(i);
        }
    }
    int dp[num.size() + 5][2007];
    FOR(j,0,num.size() + 1){
        FOR(k,0,2005){
            dp[j][k] = 1e9;
        }
    }
    FOR(i,0,2005){
        dp[0][i] = i;
    }
    //cout<<num.size() <<" " <<V.size() <<"\n";
    int zer = 0;
    FOR(i,0,num.size()){
        int p = pref[num[i]];
        int poz = V.size() + 2 - 1;
        int akt = V[num[i]];
        if(i == 0){
            poz = V.size();
            FOR(j,0,2001){ 
                int w1 = akt - (poz * ((j + 1) * (j + 2) / 2)) - ((j + 2) * (j + 1) * j) / 6;
                w1 = max(w1,zer);
                int reszta = ((w1 % (((j + 1) * (j + 2)) / 2)) > 0);
                dp[i + 1][j] = j + max(zer,(w1 / (((j + 1) * (j + 2)) / 2)) + reszta);
            }
        }else if(i == num.size() - 1){
            poz = V.size();
            FOR(j,0,2001){
                if(dp[i][j] >= 2000){continue;}
                int k = 0;
                while(j + k <= 2000 && akt > ((((k + 1) * (k + 2)) / 2) * (poz + j)) + (((k + 2) * (k + 1) * k) / 6)){
                    ++k;
                }
                if(akt <= ((((k + 1) * (k + 2)) / 2) * (poz + j)) + ((k + 2) * (k + 1) * k) / 6){
                    dp[i + 1][j + k] = min(dp[i + 1][j + k],max(dp[i][j],j + k));
                }
            }
        }else{
            int s = poz - p;
            FOR(j,0,2001){
                if(dp[i][j] >= 2000){continue;}
                int k = 0;
                while(j + k <= 2000 && ((akt >= (((k + 1) * k) / 2) * (poz + j) + (k + 1) * (j + p) * s + ((k + 1) * k * (k - 1)) / 6) || (k == 0))){
                    int koszt = akt - (((k + 1) * k) / 2) * (poz + j) - (k + 1) * (j + p) * s - ((k + 1) * k * (k - 1)) / 6;
                    koszt = max(koszt,zer);
                    int reszta = ((koszt % ((k + 1) * (j + p) + ((k + 1) * k) / 2)) > 0);
                    koszt/=(k + 1) * (j + p) + ((k + 1) * k) / 2;
                    koszt+=reszta;
                    dp[i + 1][j + k] = min(dp[i + 1][j + k],max(dp[i][j],j + k + koszt));
                    ++k;
                } 
                int koszt = akt - (((k + 1) * k) / 2) * (poz + j) - (k + 1) * (j + p) * s - ((k + 1) * k * (k - 1)) / 6;
                koszt = max(koszt,zer);
                int reszta = ((koszt % ((k + 1) * (j + p) + ((k + 1) * k) / 2)) > 0);
                koszt/=(k + 1) * (j + p) + ((k + 1) * k) / 2;
                koszt+=reszta;
                dp[i + 1][j + k] = min(dp[i + 1][j + k],max(dp[i][j],j + k + koszt));
                ++k;
            }
        }
    }
    int odp = 2000;
    FOR(i,0,2001){
        odp = min(odp,dp[num.size()][i]);
    }
   // cout<<odp <<"\n";
    odp+=V.size() + 2;
    cout<<odp;
}
int32_t main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int t;
    cin>>t;
    FOR(i,0,t){
        solve();
        cout<<"\n";
    }
}