题目描述

共有 $n$ 堆石堆，每第 $i$ 堆石堆有 $s_i$ 个石头。您可以按从前往后的顺序选择一个石堆 $i$ $(3 ≤ i ≤ n)$（即不可以先选择 $j$，后选择 $i$，其中 $i<j$），并选择一个数字 $d$ $(0 ≤ d ≤ s_i)$，从 $i$ 中移动 $d$ 个石头到第 $i-1$ 堆，并移动 $2 \times d$ 个石头到 $i-2$ 堆。

试求:移动后最小堆中石头数量的最大值。

注:若某堆在移动过程中石头数量变为 $0$，仍算作一个堆。

输入格式

第一行输入一个整数 $t(1 ≤ t ≤ 2 \times 10^5)$ ,表示测试用例的数量。 每个测试用例的第一行输入一个整数 $n(3 ≤ n ≤ 2 \times 10^5)$，表示石堆的数量。 每个测试用例的第二行输入n个整数 $s_i(0 ≤ s_i ≤ 10^9)$,表示每个石堆所含的石头数。

输出格式

输出一个整数，表示最小堆可以有的最大石头数。

输入样例

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