У Чирно есть последовательность \(a\) длины \(n\). Она может выполнять каждую из следующих операций любое количество раз (возможно, ноль). Есть дополнительное условие — перед операцией текущая длина \(a\) не должна быть равна \(1\):
- Развернуть последовательность. Формально, \([a_1,a_2,\ldots,a_n]\) становится \([a_n,a_{n-1},\ldots,a_1]\) после операции.
- Заменить последовательность на её разностную последовательность. Формально, \([a_1,a_2,\ldots,a_n]\) становится \([a_2-a_1,a_3-a_2,\ldots,a_n-a_{n-1}]\) после операции.
Найдите максимальную возможную сумму элементов \(a\) после операций.
Выходные данные
Для каждого набора входных данных выведите целое число, представляющее максимальную возможную сумму.
Примечание
В первом наборе входных данных Чирно не может выполнить ни одной операции, поэтому ответ равен \(-1000\).
Во втором наборе входных данных Чирно сначала разворачивает последовательность, затем заменяет последовательность на её разностную последовательность: \([5,-3]\to[-3,5]\to[8]\). Можно доказать, что это максимизирует сумму, поэтому ответ равен \(8\).
В третьем наборе входных данных Чирно может не выполнять операции, поэтому ответ равен \(1001\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|