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
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const LL NB = 2e5 + 10;
constexpr LL base = 1 << 20;
LL sum_tree[2*base];  

void update_sum(LL pos, LL val)
{
    pos += base;
    sum_tree[pos] = val;
    pos /= 2;
    while(pos)
    {
        sum_tree[pos] = sum_tree[pos*2] + sum_tree[pos*2+1];
        pos /= 2;
    }
}

LL query_sum(LL a, LL b)
{
    a += base;
    b += base;
    LL sum = 0;
    while(a <= b)
    {
        if(a % 2 == 1)
            sum += sum_tree[a++];
        if(b % 2 == 0)
            sum += sum_tree[b--];
        a /= 2;
        b /= 2;
    }
    return sum;
}

LL tab[NB];

LL cntGames(LL n, LL building)
{
    LL cntMID = query_sum(building, building);
    LL cntL = query_sum(1, building-1);
    LL cntR = query_sum(building+1, n);
    
    LL games = 0;
    if (cntMID >= 3LL)
        games += (LL)cntMID * (cntMID - 1LL) * (cntMID - 2LL) / 6LL;
    if (cntMID >= 2LL)
        games += (LL)cntMID * (cntMID - 1LL) / 2LL * (cntL + cntR);
    games += (LL)cntMID * cntL * cntR;
    return games;
}

bool check(LL ile, LL n)
{
    memset(sum_tree, 0, sizeof(sum_tree));
    LL cnt = ile / n;
    LL rem = ile - cnt * n;
    
    for (LL i = 1; i <= n; i++)
    {
        LL val = cnt;
        if(rem > 0)
        {
            val++;
            rem--;
        }
        update_sum(i, val);
    }

    for (LL i = 1; i <= n; i++)
    {
        if(tab[i] == 0)
            continue;
        LL x = cntGames(n, i); 
        if(x < tab[i])
            return false;
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    LL t;
    cin >> t;
    while (t--)
    {
        LL n;
        cin >> n;
        for (LL i = 1; i <= n; i++)
            cin >> tab[i];
        LL L = 1, P = 1e9, res = 0;
        while(L <= P)
        {
            LL mid = (L + P) / 2;
            if(check(mid, n))
            {
                res = mid;
                P = mid - 1;
            }
            else
                L = mid + 1;
        }
        cout << res << "\n";
    }
    return 0;
}