有 $$$n$$$ 堆石头。第 $$$i$$$ 堆有 $$$h_i$$$ 石头。您想要通过执行以下过程一次来更改堆中石头的数量:
- 按此顺序从 $$$3$$$-rd 堆到 $$$n$$$-th 堆遍历堆。
- 令 $$$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
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]$$$。