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
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define sn second

typedef long long ll;
typedef vector<int> VI;
typedef vector<char> VC;
typedef pair<int, int> PI;

const int MAX_PPL = 183;

vector<ll> CHOOSE3(MAX_PPL + 1);
vector<ll> CHOOSE2(MAX_PPL + 1);

void init() {
  CHOOSE3[0] = 0;
  CHOOSE2[0] = 0;
  for (int i = 1; i <= MAX_PPL; i++) {
    CHOOSE3[i] = i * (i - 1) * (i - 2) / 6;
    CHOOSE2[i] = i * (i - 1) / 2;
  }
}

ll games(ll a, ll left, ll right) {
  return CHOOSE3[a] + CHOOSE2[a] * (left + right) + a * left * right;
}

bool try_allocate(int total, int n, vector<ll> &A) {
  // cout << "Try: " << total << endl;
  ll l = 0;
  for (int i = 0; i < n; i++) {
    int p = -1;
    ll g = -1;
    ll right = -1;
    int ppl_left = total - l;
    int min_j = 0;
    int max_j = min(MAX_PPL, ppl_left);

    while (min_j <= max_j) {
      int j = (min_j + max_j) / 2;
      right = i == n - 1 ? 0 : ppl_left - j;
      g = games((ll)j, l, right);
      if (g >= A[i]) {
        p = j;
        max_j = j - 1;
      } else {
        min_j = j + 1;
      }
    }
    // cout << "\t" << i << " (" << A[i] << ") " << p << " " << g << endl;
    // cout << "\t\t" << CHOOSE3[p] << " " << CHOOSE2[p] * (l + right) << " "
    //      << (l + right) << " " << l << " " << right << " " << p * l * right
    //      << endl;

    if (p == -1) {
      return false;
    }
    l += p;
  }
  return true;
}

int main() {
  int T;
  cin >> T;

  init();

  for (int t = 0; t < T; t++) {
    int N;
    cin >> N;
    vector<ll> A(N);
    bool all_zero = true;
    for (int i = 0; i < N; i++) {
      cin >> A[i];
      if (A[i] != 0) {
        all_zero = false;
      }
    }

    if (all_zero) {
      cout << 0 << endl;
      continue;
    }

    int res = 0;
    int max_ppl = MAX_PPL * N;
    int min_ppl = 1;

    while (min_ppl <= max_ppl) {
      int mid = (min_ppl + max_ppl) / 2;
      if (try_allocate(mid, N, A)) {
        res = mid;
        max_ppl = mid - 1;
      } else {
        min_ppl = mid + 1;
      }
    }
    cout << res << endl;
  }

  return 0;
}