C. Сбалансированные кучки камней
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В ряд находятся $$$n$$$ кучек камней. В $$$i$$$-й кучке изначально $$$h_i$$$ камней. Вы хотите изменить число камней в кучках, выполнив следующий процесс один раз:

  • Вы идете по кучкам от $$$3$$$-й до $$$n$$$-й, в таком порядке.
  • Пусть $$$i$$$ — номер текущей кучки.
  • Вы можете выбрать целое число $$$d$$$ ($$$0 \le 3 \cdot d \le h_i$$$), переместить $$$d$$$ камней из $$$i$$$-й кучки в $$$(i - 1)$$$-ю кучку, и $$$2 \cdot d$$$ камней из $$$i$$$-й кучки в $$$(i - 2)$$$-ю.
  • Таким образом, $$$h_i$$$ уменьшается на $$$3 \cdot d$$$, $$$h_{i - 1}$$$ увеличивается на $$$d$$$, и $$$h_{i - 2}$$$ увеличивается на $$$2 \cdot d$$$.
  • Вы можете выбирать различные или одинаковые $$$d$$$ для различных операций. Некоторые кучки могут стать пустыми, но они все еще считаются за кучки.

Какое наибольшее число камней в наименьшей кучке может получиться после завершения процесса?

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2\cdot 10^5$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$).

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$h_1, h_2, h_3, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите максимальное число камней, которое может содержать наименьшая по количеству камней кучка после завершения процесса.

Пример
Входные данные
4
4
1 2 10 100
4
100 100 100 1
5
5 1 1 1 8
6
1 2 3 4 5 6
Выходные данные
7
1
1
3
Примечание

В первом примере изначально размеры кучек равны $$$[1, 2, 10, 100]$$$. Мы можем перемещать камни следующим образом.

  • переместить $$$3$$$ и $$$6$$$ камней с $$$3$$$-й кучки на $$$2$$$-ю и $$$1$$$-ю кучки соответственно. Размеры кучек будут равны $$$[7, 5, 1, 100]$$$;
  • Переместить $$$6$$$ и $$$12$$$ камней с последней кучки на $$$3$$$-ю и $$$2$$$-ю кучки соответственно. Размеры кучек будут равны $$$[7, 17, 7, 82]$$$.

Во втором наборе размер последней кучки равен $$$1$$$ и мы не можем его увеличить.

В третьем наборе оптимально не перемещать никакие камни.

В четвертом примере можно достичь состояния, в котором размеры кучек равны $$$[3, 5, 3, 4, 3, 3]$$$.