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

using namespace std;

#define _DEBUG
#ifdef _DEBUG
template<typename T1, typename T2> auto& operator<<(ostream& o, pair<T1, T2> a) { return o << "(" << a.first << ", " << a.second << ")"; }
template<typename T, typename OS> auto& operator<<(OS& o, T a) { o << "{"; for(auto b : a) o << b << ", "; return o << "}"; }
#define dbg(x...) cerr << "[" #x "]: ", [](auto... args) { ((cerr << args << ", "),...) << "\n"; }(x)
#else
#define dbg(...)
#endif

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define F first
#define S second

using ll = __int128_t;
using ld = long double;
using pll = pair<ll,ll>;
using vi = vector<int>;

ll f(ll n, ll before, ll v) {
  assert(n - before - v >= 0);
  ll ans = 0;
  if(v > 2) {
    ans += v * (v - 1) * (v - 2) / 6;
  }
  if(v > 1) {
    ans += (n - v) * v * (v - 1) / 2;
  }
  ans += before * (n - before - v) * v;
  return ans;
}

ll findMax(ll n, ll before) {
  ll l = 0;
  ll r = n - before;
  while(l < r) {
    ll p1 = (l + r) / 2;        
    ll p2 = p1 + 1;
    ll v1 = f(n, before, p1);
    ll v2 = f(n, before, p2);
    if(v1 < v2) {
      l = p2;
    }
    else {
      r = p1;
    }
  }
  return l;
}

bool check(const vector<int>& vs, ll n) {
  ll before = 0;

  for(int i = 0; i < vs.size(); i++) {
    ll l = 0;
    ll r = findMax(n, before);

    if(f(n, before, r) < vs[i]) {
      return false;
    }

    while(l < r) {
      int mid = (l + r) / 2;
      if(f(n, before, mid) < vs[i]) {
        l = mid + 1;
      }
      else {
        r = mid;
      }
    }
    before += l;
  }
  return true;
}

void solve() {
  int n;
  cin >> n;
  vector<int> vs(n);
  for(auto& v : vs) {
    cin >> v;
  }

  ll l = 3;
  ll r = 200 * n;

  while(l < r) {
    int mid = (l + r) / 2;
    if(check(vs, mid)) {
      r = mid;
    }
    else {
      l = mid + 1;
    }
  }

  cout << (int64_t)l;
}

// 9000 * n

int main() {
  // for(int i = 0; i < 1000000; i++) {
    // test();
  // }
  // return 0;
  //test();
  cin.tie(0)->sync_with_stdio(0);
  int t = 1;
  cin >> t;
  while(t--) {
    solve();
    cout << "\n";
  }
  return 0;
}