Дан массив \(a\) состоящий из \(n\) элементов, найдите максимально возможную сумму, которая может быть у массива после выполнения следующей операции любое количество раз:
- Выбрать \(2\) соседних элемента и поменять их знаки. Иными словами, выбрать индекс \(i\) такой, что \(1 \leq i \leq n - 1\) и присвоить \(a_i = -a_i\) и \(a_{i+1} = -a_{i+1}\).
Выходные данные
Для каждого набора входных данных выведите максимально возможную сумму, которая может получится у массива, если мы применим описанную выше операцию любое количество раз.
Примечание
В первом наборе, выполнив операцию над первыми двумя элементами, мы можем изменить массив с \([-1, -1, -1]\) на \([1, 1, -1]\). Можно доказать, что этот массив дает максимально возможную сумму, которая равна \(1 + 1 + (-1) = 1\).
Во втором наборе, выполнив операцию над \(-5\) и \(0\), мы изменим массив с \([1, 5, -5, 0, 2]\) на \([1, 5, -(-5), -0, 2] = [1, 5, 5, 0, 2]\), который имеет максимальную сумму, так как все элементы неотрицательны. Так, ответ: \(1 + 5 + 5 + 0 + 2 = 13\).
В третьем наборе массив уже содержит только положительные числа, поэтому выполнять операции не нужно. Ответ — это просто сумма всего массива, которая равна \(1 + 2 + 3 = 6\).