Вам дан массив чисел \(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\).
Вам нужно вывести минимальную стоимость массива после блокировки.
Выходные данные
Для каждого набора входных данных выведите одно число — минимальную стоимость блокировки массива.
Примечание
Первый набор совпадает с массивом из условия. Чтобы получить стоимость \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
1 4 5 3 3 2
5
1 2 3 4 5
6
4 1 6 3 10 7
|
7
5
11
|