У Чирно есть последовательность \(a\) длины \(n\). Она может выполнять каждую из следующих операций любое количество раз (возможно, ноль). Есть дополнительное условие — перед операцией текущая длина \(a\) не должна быть равна \(1\):
Найдите максимальную возможную сумму элементов \(a\) после операций.
Первая строка входных данных содержит одно целое число \(t\) (\(1 \leq t \leq 100\)) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1\le n\le 50\)) — длина последовательности \(a\).
Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(a_1,a_2,\ldots,a_n\) (\(|a_i|\le 1000\)) — последовательность \(a\).
Для каждого набора входных данных выведите целое число, представляющее максимальную возможную сумму.
В первом наборе входных данных Чирно не может выполнить ни одной операции, поэтому ответ равен \(-1000\).
Во втором наборе входных данных Чирно сначала разворачивает последовательность, затем заменяет последовательность на её разностную последовательность: \([5,-3]\to[-3,5]\to[8]\). Можно доказать, что это максимизирует сумму, поэтому ответ равен \(8\).
В третьем наборе входных данных Чирно может не выполнять операции, поэтому ответ равен \(1001\).
5 1 -1000 2 5 -3 2 1000 1 9 9 7 9 -9 9 -8 7 -8 9 11 678 201 340 444 453 922 128 987 127 752 0
-1000 8 1001 2056 269891
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач