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
#include <iostream>

using namespace std;
typedef long long ll;

const int N = 2e5+9;
int A[N];

ll f(ll l, ll x, ll r) {
    return x*(x-1)/2*(x-2)/3+x*(x-1)/2*(l+r)+l*x*r;
}

bool check(int s, int n) {
    int l = 0;
    for(int i = 1; i < n; ++i) {
        if(i >= 1000 && n-i >= 1000 && i < n-i) {
            l += n-i-i;
            i = n-i;
        }
        int x = 1;
        int r = s-l-x;
        while(r >= n-i && f(l, x, r) < A[i]) {
            x++;
            r--;
        }
        if(r < n-i) {
            return false;
        }
        l += x;
    }
    return (f(l, s-l, 0) >= A[n]);
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        int m = 0;
        for(int i = 1; i <= n; ++i) {
            int a; cin >> a;
            if(a != 0) {
                A[++m] = a;
            }
        }
        int res = -1;
        for(int i = m; i <= m+2000; ++i) {
            if(check(i, m)) {
                res = i;
                break;
            }
        }
        cout << res << "\n";
    }

    return 0;
}