Вам дан массив \(a\) из \(n\) целых чисел. Вы должны выполнить следующие две операции с массивом (сначала первую, затем вторую):
- Произвольно переставить элементы массива или оставить порядок его элементов без изменений.
- Выбрать не более одного отрезка подряд идущих элементов и заменить знаки всех элементов на этом отрезке на противоположные. Формально, вы можете выбрать пару индексов \(l, r\) такие, что \(1 \le l \le r \le n\) и присвоить \(a_i = -a_i\) для всех \(l \le i \le r\). Заметим, что вы можете не выбирать пару индексов и оставить все знаки элементов без изменений.
Какова максимальная сумма элементов массива после последовательного выполнения двух операций (сначала первой, затем второй)?
Примечание
В первом наборе входных данных вы можете сначала переставить массив, чтобы получился \([3,-2,-3]\) (операция 1), затем выбрать \(l = 2, r = 3\) и получить сумму \(3 + -((-2) + (-3)) = 8\) (операция 2).
Во втором наборе входных данных вы можете ничего не делать при выполнении обеих операций и получить сумму \(0\).
В третьем наборе входных данных вы можете ничего не делать при выполнении обеих операций и получить сумму \(0 + 1 = 1\).
В четвертом наборе входных данных вы можете сначала оставить порядок неизменным (операция 1), затем выбрать \(l = 1, r = 1\) и получить сумму \(-(-99) = 99\) (операция 2).
В пятом наборе входных данных вы можете сначала оставить порядок неизменным (операция 1), затем выбрать \(l = 2, r = 3\) и получить сумму \(10 + -((-2) + (-3)) + 7 = 22\) (операция 2).
В шестом наборе входных данных вы можете сначала оставить порядок неизменным (операция 1), затем выбрать \(l = 1, r = 5\) и получить сумму \(-((-1)+(-2)+(-3)+(-4)+(-5))=15\) (операция 2).