D. Блокировка элементов
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив чисел $$$a_1, a_2, \ldots, a_n$$$. Ваша задача — заблокировать некоторые элементы массива так, чтобы минимизировать его стоимость. Допустим, вы заблокировали элементы с индексами $$$1 \leq b_1 < b_2 < \ldots < b_m \leq n$$$. Тогда стоимость массива вычисляется как максимум из:

  • суммы заблокированных элементов, то есть $$$a_{b_1} + a_{b_2} + \ldots + a_{b_m}$$$.
  • максимума из сумм на частях, на которые распадается массив, если удалить заблокированные элементы. То есть максимум из сумм на следующем ($$$m + 1$$$)-ом подотрезке: [$$$1, b_1 − 1$$$], [$$$b_1 + 1, b_2 − 1$$$], [$$$\ldots$$$], [$$$b_{m−1} + 1, b_m - 1$$$], [$$$b_m + 1, n$$$] (сумма чисел на подотрезке вида [$$$x,x − 1$$$] полагается равной $$$0$$$).

К примеру, если $$$n = 6$$$, исходный массив равен [$$$1, 4, 5, 3, 3, 2$$$], и вы заблокировали элементы на позициях $$$2$$$ и $$$5$$$, то стоимость массива будет равна максимуму из суммы заблокированных элементов ($$$4 + 3 = 7$$$) и сумм на отрезках ($$$1$$$, $$$5 + 3 = 8$$$, $$$2$$$) что равно $$$\max(7,1,8,2) = 8$$$.

Вам нужно вывести минимальную стоимость массива после блокировки.

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

В первой строке входных данных вводится одно число $$$t$$$ ($$$1 \leq t \leq 30\,000$$$) — количество запросов.

Каждый набор входных данных состоит из двух строк. В первой строке вводится число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — длина массива $$$a$$$. Во второй строке вводится $$$n$$$ элементов $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — массив $$$a$$$.

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

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

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

Пример
Входные данные
3
6
1 4 5 3 3 2
5
1 2 3 4 5
6
4 1 6 3 10 7
Выходные данные
7
5
11
Примечание

Первый набор совпадает с массивом из условия. Чтобы получить стоимость $$$7$$$ нужно заблокировать элементы на позициях $$$2$$$ и $$$4$$$, В таком случае стоимость массива вычислится как максимум из:

  • суммы заблокированных элементов, которая равна $$$a_2 + a_4 = 7$$$.
  • максимума из сумм на частях, на которые распадается массив, если убрать заблокированные, то есть максимум из $$$a_1$$$, $$$a_3$$$, $$$a_5 + a_6 = \max(1,5,5) = 5$$$.

То есть стоимость равна $$$\max(7,5) = 7$$$.

Во втором наборе можно заблокировать элементы на позициях $$$1$$$ и $$$4$$$.

В третьем наборе чтобы получить ответ $$$11$$$ можно заблокировать элементы на позициях $$$2$$$ и $$$5$$$. Есть и другие способы получить такой ответ, например заблокировать позиции $$$4$$$ и $$$6$$$.