Balanced Stone Heaps

题目描述

那里有成堆的石头。 第 $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$ 。

输出格式

对于每个测试用例，打印最小堆可以包含的石头的最大数量。

样例 #1

样例输入 #1

4
4
1 2 10 100
4
100 100 100 1
5
5 1 1 1 8
6
1 2 3 4 5 6

样例输出 #1

7
1
1
3

提示

在第一个测试用例中，初始堆大小为 $[1, 2, 10, 100]$ 。我们可以这样移动石头。

-将 $3$ 和 $6$ 从 $3$ -rd堆分别移动到 $2$ -nd和 $1$ 堆。堆大小将为 $[7, 5, 1, 100]$ ； -将 $6$ 和 $12$ 从最后一个堆分别移动到 $3$ -rd和 $2$ -nd堆。堆大小将为 $[7, 17, 7, 82]$ 。

在第二个测试用例中，最后一个堆是 $1$ ，我们不能增加它的大小。

在第三个测试用例中，最好不要移动任何石头。

在最后一个测试用例中，堆的最终可实现配置可以是 $[3, 5, 3, 4, 3, 3]$ 。