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
#include <cstdio>
#include <vector>

using namespace std;

const int MAX_PPL_TOTAL = 1 << 30;
const int MAX_PPL_IN_SINGLE_HOUSE = 1 << 10;

struct Checkable {
  virtual bool check(long long n) = 0;
};

long long pascal_triangle[MAX_PPL_IN_SINGLE_HOUSE + 1][4];

int binomial(int n, int k) { return pascal_triangle[n][k]; }

int b_search(int max_n, Checkable &condition) {
  int left = 0, right = max_n;
  int result = right;

  while (right >= left) {
    int mid = (left + right) / 2;

    // printf("l: %d r: %d m: %d\n", left, right, mid);

    if (condition.check(mid)) {
      result = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return result;
};

struct HouseChecker : Checkable {
  long long ppl_used;
  long long ppl_left;
  long long value;

  bool check(long long n) {
    long long left_on_right = ppl_left - n;

    // printf("l: %lld r: %lld lor: %lld n: %lld\n", ppl_used, ppl_left,
    // left_on_right, n);

    if (left_on_right < 0) {
      return true;
    }

    return ppl_used * n * left_on_right + ppl_used * binomial(n, 2) +
               binomial(n, 2) * left_on_right + binomial(n, 3) >=
           value;
  };
};

struct Street : Checkable {
  vector<int> houses;

  Street(vector<int> &houses) { this->houses = houses; }

  bool check(long long n) {
    long long left = 0, right = n;

    // printf("TOTAL PPL: %lld\n", n);

    for (int i = 0; i < houses.size(); i++) {
      auto house = houses[i];
      HouseChecker house_check;

      house_check.ppl_used = left;
      house_check.ppl_left = right;
      house_check.value = house;

      // printf("HOUSE: %d\n", house);
      long long smallest = b_search(MAX_PPL_IN_SINGLE_HOUSE, house_check);

      left += smallest;
      right -= smallest;

      if (right < 0) {
        // printf("TOTAL PPL FALSE: %lld\n", n);
        return false;
      }
    }

    return true;
  };
};

int solve(vector<int> &houses) {
  Street street(houses);

  return b_search(MAX_PPL_TOTAL, street);
};

void process_test() {
  int n;
  vector<int> houses;

  scanf("%d", &n);
  houses.resize(n);

  for (int i = 0; i < n; i++) {
    scanf("%d", &houses[i]);
  }

  printf("%d\n", solve(houses));
}

int main() {
  int t;

  scanf("%d", &t);

  pascal_triangle[0][0] = 1;

  for (int k = 0; k <= 3; k++) {
    for (int n = 1; n <= MAX_PPL_IN_SINGLE_HOUSE; n++) {
      if (k == 0) {
        pascal_triangle[n][k] = 1;
      } else {
        pascal_triangle[n][k] =
            pascal_triangle[n - 1][k] + pascal_triangle[n - 1][k - 1];
      }
    }
  }

  // for (int k = 0; k <= 3; k++) {
  //   for (int n = 1; n <= 16; n++) {
  //     printf("%lld ", pascal_triangle[n][k]);
  //   }
  //   puts("");
  // }

  // printf("%d\n", MAX_PPL_TOTAL);
  // printf("%d\n", MAX_PPL_IN_SINGLE_HOUSE);

  for (int i = 0; i < t; i++) {
    process_test();
  }
}