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

В ряд расположены $$$n$$$ кусочков торта. $$$i$$$-й кусочек имеет вес $$$a_i$$$ ($$$1 \leq i \leq n$$$).

Ценностью торта называется максимальный суммарный вес двух подряд идущих кусочков (т. е. $$$\max(a_1+a_2,\, a_2+a_3,\, \ldots,\, a_{n-1} + a_{n})$$$).

Вы хотите сделать ценность торта как можно больше. Вы можете выполнить следующую операцию не более одного раза (иначе торт будет испорчен):

  • Выберите последовательный подотрезок $$$a[l, r]$$$ кусочков торта ($$$1 \leq l \leq r \leq n$$$) и разверните его.

Подотрезком $$$a[l, r]$$$ массива $$$a$$$ называется последовательность $$$a_l, a_{l+1}, \dots, a_r$$$. Если ее развернуть, массив станет равным $$$a_1, a_2, \dots, a_{l-2}, a_{l-1}, \underline{a_r}, \underline{a_{r-1}}, \underline{\dots}, \underline{a_{l+1}}, \underline{a_l}, a_{r+1}, a_{r+2}, \dots, a_{n-1}, a_n$$$.

Например, если веса кусочков изначально равны $$$[5, 2, 1, 4, 7, 3]$$$, можно развернуть подотрезок $$$a[2, 5]$$$, получив $$$[5, \underline{7}, \underline{4}, \underline{1}, \underline{2}, 3]$$$. Тогда ценность торта будет равна $$$5 + 7 = 12$$$ (а до разворота она была равна $$$4+7=11$$$).

Найдите максимально возможную ценность торта после выполнения не более чем одной операции.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 1000$$$) — количество кусочков торта.

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

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

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

Пример
Входные данные
5
6
5 2 1 4 7 3
3
32 78 78
3
69 54 91
8
999021 999021 999021 999021 999652 999021 999021 999021
2
1000000000 1000000000
Выходные данные
12
156
160
1998673
2000000000
Примечание

В первом примере после выполнения разворота подотрезка $$$a[2, 5]$$$ получится торт с весами $$$[5, \underline{7}, \underline{4}, \underline{1}, \underline{2}, 3]$$$. Ценность такого торта равна $$$\max(5+7, 7+4, 4+1, 1+2, 2+3) = 12$$$. Это максимально возможная ценность, которую можно получить, выполнив операцию не более одного раза.

Во втором тесте оптимально не делать ни одной операции. Ценность равна $$$78+78 = 156$$$.

В третьем примере после разворота подотрезка $$$a[1, 2]$$$ получится торт с весами $$$[\underline{54}, \underline{69}, 91]$$$. Ценность получившегося торта равна $$$\max(54+69, 69+91) = 160$$$. Невозможно получить ценность выше $$$160$$$, выполнив не более одной операции.