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

Призрак Джа снова играет с резиновыми утятами! В ряд слева направо расставлены $$$n$$$ кучек резиновых утят. Изначально $$$i$$$-я кучка содержит $$$a_i$$$ резиновых утят.

Пока последовательность $$$a$$$ не отсортирована в неубывающем порядке, Джа обязан выполнять следующую операцию:

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

    Формально, выбрать индекс $$$i$$$ такой, что $$$1\le i \lt n$$$ и $$$a_i \gt a_{i+1}$$$. Затем заменить соседнюю пару $$$(a_i,a_{i+1})$$$ на $$$(a_{i+1},a_i+a_{i+1})$$$.

Например, если две соседние кучки содержат $$$7$$$ и $$$3$$$ резиновых утёнка, то после операции они содержат $$$3$$$ и $$$10$$$ резиновых утят.

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

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

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — количество утят в каждой кучке.

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

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

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

Пример
Входные данные
10
4
1 2 2 5
2
7 3
3
3 2 1
5
2 2 1 3 3
4
3 1 4 2
5
1 4 3 2 5
6
6 2 5 1 4 3
7
2 7 1 6 3 5 4
8
8 1 7 2 6 3 5 4
5
1000000000 999999999 999999998 999999997 999999996
Выходные данные
5
10
6
3
6
14
21
26
36
4999999990
Примечание

В преобразованиях ниже два подчёркнутых числа — это соседняя пара, только что полученная в результате операции.

В первом наборе входных данных последовательность уже отсортирована в неубывающем порядке. Поэтому Джа не выполняет ни одной операции, и ответ равен $$$5$$$.

Во втором наборе входных данных у Джа есть только одна возможная операция: $$$$$$ [7,3]\to [\underline{3},\underline{10}]. $$$$$$ После этого последовательность отсортирована, поэтому ответ равен $$$10$$$.

В третьем наборе входных данных Джа может выполнить следующие операции: $$$$$$ [3,2,1]\to [\underline{2},\underline{5},1]\to [2,\underline{1},\underline{6}]\to [\underline{1},\underline{3},6]. $$$$$$ Наибольшая кучка содержит $$$6$$$ утят. Если Джа сначала выберет последние две кучки, наибольшая кучка в конце будет содержать $$$7$$$ утят. Следовательно, ответ равен $$$6$$$.

В четвёртом наборе входных данных Джа не может выбрать первые две кучки в начале, так как $$$2$$$ не больше $$$2$$$. Один из возможных процессов: $$$$$$ [2,2,1,3,3]\to [2,\underline{1},\underline{3},3,3]\to [\underline{1},\underline{3},3,3,3]. $$$$$$ Таким образом, ответ равен $$$3$$$.

В пятом наборе входных данных один из оптимальных процессов: $$$$$$ [3,1,4,2]\to [\underline{1},\underline{4},4,2]\to [1,4,\underline{2},\underline{6}]\to [1,\underline{2},\underline{6},6]. $$$$$$ Следовательно, ответ равен $$$6$$$.