CF1623C.Balanced Stone Heaps

There are $n$ heaps of stone. The $i$-th heap has $h_i$ stones. You want to change the number of stones in the heap by performing the following process once:

• You go through the heaps from the $3$-rd heap to the $n$-th heap, in this order.
• Let $i$ be the number of the current heap.
• You can choose a number $d$ ($0 \le 3 \cdot d \le h_i$), move $d$ stones from the $i$-th heap to the $(i - 1)$-th heap, and $2 \cdot d$ stones from the $i$-th heap to the $(i - 2)$-th heap.
• So after that $h_i$ is decreased by $3 \cdot d$, $h_{i - 1}$ is increased by $d$, and $h_{i - 2}$ is increased by $2 \cdot d$.
• You can choose different or same $d$ for different operations. Some heaps may become empty, but they still count as heaps.

What is the maximum number of stones in the smallest heap after the process?

有 $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$ 值；某些堆可能变为零颗石子，但仍视为有效石子堆。

问：经过该过程后，所有堆中最小堆的石子数量的最大可能值是多少？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2\cdot 10^5$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$).

The second lines of each test case contains $n$ integers $h_1, h_2, h_3, \ldots, h_n$ ($1 \le h_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print the maximum number of stones that the smallest heap can contain.

对于每个测试用例，输出最小堆中所能包含的石头的最大数量。

In the first test case, the initial heap sizes are $[1, 2, 10, 100]$. We can move the stones as follows.

• move $3$ stones and $6$ from the $3$-rd heap to the $2$-nd and $1$ heap respectively. The heap sizes will be $[7, 5, 1, 100]$;
• move $6$ stones and $12$ stones from the last heap to the $3$-rd and $2$-nd heap respectively. The heap sizes will be $[7, 17, 7, 82]$.

In the second test case, the last heap is $1$, and we can not increase its size.

In the third test case, it is better not to move any stones.

In the last test case, the final achievable configuration of the heaps can be $[3, 5, 3, 4, 3, 3]$.

在第一个测试用例中，初始堆的石子数量为 $[1, 2, 10, 100]$。我们可以按如下方式移动石子：

• 将第 $3$ 堆中的 $3$ 颗石子移至第 $2$ 堆，再将其中 $6$ 颗石子移至第 $1$ 堆。堆的石子数量变为 $[7, 5, 1, 100]$；
• 将最后一堆（即第 $4$ 堆）中的 $6$ 颗石子移至第 $3$ 堆，再将其中 $12$ 颗石子移至第 $2$ 堆。堆的石子数量变为 $[7, 17, 7, 82]$。

在第二个测试用例中，最后一堆的石子数为 $1$，我们无法增大其大小。

在第三个测试用例中，最优策略是不移动任何石子。

在最后一个测试用例中，堆所能达到的最终状态可以是 $[3, 5, 3, 4, 3, 3]$。