Вы нашли \(n\) волшебных частиц, которые расположены друг за другом в ряд и имеют целочисленные заряды \(c_1,\dots,c_n\). У вас также есть устройство, которое позволяет производить следующую операцию:
- Выбрать частицу и удалить её из последовательности. Оставшиеся частицы сдвинутся, чтобы заполнить образовавшийся разрыв между ними. Если перед удалением частицы непосредственно слева и непосредственно справа от неё были расположены частицы с зарядами \(x\) и \(y\) соответственно, то они войдут в реакцию и объединятся в одну частицу с зарядом \(x+y\).
Например, если последовательность зарядов частиц была \([-3,1,4,-1,5,-9]\), то после выполнения операции над \(4\)-й частицей последовательность преобразуется в \([-3,1,9,-9]\).
Если после этого использовать устройство на \(1\)-й частице в этом новом порядке, то последовательность станет равна \([1,9,-9]\).
Вам нужно выполнять операции до тех пор, пока в последовательности не останется ровно одна частица. Чему равен максимально возможный заряд этой частицы?
Выходные данные
Для каждого набора входных данных выведите одно число, равное максимально возможному заряду последней оставшейся частицы.
Примечание
В первом наборе входных данных оптимальная стратегия выглядит так: использовать устройство на \(4\)-й частице, затем на \(1\)-й (как описано в условии), потом на \(3\)-й, и наконец на \(1\)-й.
Во втором наборе входных данных оптимальная стратегия выглядит так: использовать устройство на \(4\)-й частице, после чего последовательность преобразуется в \([998244353,998244353,1996488706]\), затем на \(2\)-й частице, после чего последовательность станет равна \([2994733059]\). Проследите за переполнением целочисленного типа.
В третьем наборе входных данных есть всего одна частица, так что операций применять нельзя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
-3 1 4 -1 5 -9
5
998244353 998244353 998244353 998244353 998244353
1
-2718
|
9
2994733059
-2718
|