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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
#include <numeric>

using namespace std;

constexpr long long N = 200005L;
constexpr long long M = 200100L;

long long A[N];

long long nad3[M];
long long nad2[M];

static long long szukaj3(long long left, long long right, long long value) {
    if (left > right) {
        return -1;
    }

    long long srodek = (left + right) / 2;

    if (nad3[srodek - 1] < value && value <= nad3[srodek]) {
         return srodek;
    }

    if (nad3[srodek] >= value) {
        return szukaj3(left, srodek - 1, value);
    }
    else {
        return szukaj3(srodek + 1, right, value);
    }
}

static long long szukaj3(long long value) {
    return szukaj3(1, M - 2, value);
}


static long long f1(long long a, long long n) {
    long long result = nad2[a] * (n - a) + nad3[a];
    return result;
}

static long long rozwiaz_skrajna(long long left, long long right, long long n, long long value) {
    if (left > right) {
        return -1L;
    }

    long long a = (left + right) / 2;
    if (a == 0) return -1;

    long long fa = f1(a, n);
    long long fa1 = f1(a - 1, n);

    if (fa >= value && fa1 < value) {
        return a;
    }

    if (fa < value) {
        return rozwiaz_skrajna(a + 1, right, n, value);
    }
    else {
        return rozwiaz_skrajna(left, a - 1, n, value);
    }
}

static long long f2(long long a, long long n, long long suma) {
    long long result = a * suma * (n - suma - a) + nad2[a] * (n - a) + nad3[a];
    return result;
}

static long long rozwiaz_srodkowa(long long left, long long right, long long n, long long value, long long suma) {
    if (left > right) {
        return -1L;
    }

    long long a = (left + right) / 2;
    if (a == 0) return -1;

    long long fa = f2(a, n, suma);
    long long fa1 = f2(a - 1, n, suma);

    if (fa >= value && fa1 < value) {
        return a;
    }

    if (fa < value) {
        return rozwiaz_srodkowa(a + 1, right, n, value, suma);
    }
    else {
        return rozwiaz_srodkowa(left, a - 1, n, value, suma);
    }
}


long long n;
long long suma;
long long first;
long long last;

static bool czy_jest_ok(long long testowana) {
    long long ile_minumum = 0L;
    long long suma_z_lewej = 0L;
    long long suma_z_prawej = 0L;

    //printf("%lld\n", testowana);

    for (long long i = first; i <= last; i++) {
        long long index = i - first;
        bool lewa = true;
        if (index % 2 == 0) {
            index = first + (index / 2);
        }
        else {
            index = last - (index / 2);
            lewa = false;
        }
        long long odleglosc = min(index - first, last - index);

        if (A[index] == 0) continue;

        if (odleglosc == 0) {
            long long najmniejsza_mozliwa = 2;
            long long najwieksza_pewna = szukaj3(A[index]);
            long long minimum = rozwiaz_skrajna(najmniejsza_mozliwa, najwieksza_pewna, testowana, A[index]);
            //printf("testowane = %lld index = %lld minumum = %lld\n", testowana, index, minimum);
            ile_minumum += minimum;
            if (lewa) {
                suma_z_lewej += minimum;
            }
            else {
                suma_z_prawej += minimum;
            }
        }
        else {
            long long minimum = 0;
            if (suma_z_lewej * suma_z_prawej >= A[index]) {
                minimum = 1;
            }
            else {
                long long najmniejsza_mozliwa = 1;
                long long najwieksza_pewna = szukaj3(A[index]);
                minimum = rozwiaz_srodkowa(najmniejsza_mozliwa, najwieksza_pewna, testowana, A[index], lewa ? suma_z_lewej : suma_z_prawej);
            }
            //printf("testowane = %lld index = %lld minumum = %lld\n", testowana, index, minimum);
            ile_minumum += minimum;
            if (lewa) {
                suma_z_lewej += minimum;
            }
            else {
                suma_z_prawej += minimum;
            }
        }

        if (testowana < ile_minumum) return false;
    }

    return testowana >= ile_minumum;
}

long long binary_search(long long left, long long right, long long minmin) {
    if (left > right) {
        return -1L;
    }

    long long a = (left + right) / 2;
    if (a == 0) return -1;

    if (czy_jest_ok(a) && a == minmin) {
        return a;
    }

    if (czy_jest_ok(a) && !czy_jest_ok(a - 1)) {
        return a;
    }
    if (czy_jest_ok(a)) {
        return binary_search(left, a - 1, minmin);
    }
    else {
        return binary_search(a + 1, right, minmin);
    }
}

int main() {
    int t;
    nad3[0] = 0; nad2[0] = 0;
    nad3[1] = 0; nad2[1] = 0;
    nad3[2] = 0; nad2[2] = 1;
    nad3[3] = 1; nad2[3] = 3;
    for (long long i = 4; i < M; i++) {
        long long g = gcd(i, i - 3);
        long long ii = i / g;
        long long ii2 = (i - 3) / g;

        long long g1 = gcd(i, i - 2);
        long long ii1 = i / g1;
        long long ii21 = (i - 2) / g1;

        nad3[i] = nad3[i - 1] / ii2 * ii;
        //printf("%lld %lld\n", i, nad3[i]);
        nad2[i] = nad2[i - 1] / ii21 * ii1;
    }

    //printf("%lld\n", nad3[M - 3]);

    long long MAX = M - 2;

    scanf("%d", &t);

    for (int i = 0; i < t; i++) {
        suma = 0;
        first = -1;
        last = 0;

        scanf("%d", &n);

        for (int j = 0; j < n; j++) {
            scanf("%lld", &A[j]);
            suma += A[j];

            if (A[j] > 0) {
                last = j;
                if (first == -1) {
                    first = j;
                }
            }
        }

        long long minmin = szukaj3(suma);
        long long testowana = binary_search(minmin, MAX, minmin);

        printf("%lld\n", testowana);
    }

    return 0;
}