У Ярослава есть массив, состоящий из (2·n - 1) целых чисел. За одну операцию Ярослав может поменять знак у ровно n элементов массива. Другими словами, за одну операцию Ярослав может выбрать ровно n элементов массива и каждый из них домножить на -1.
Сейчас Ярослава интересует вопрос: какую максимальную сумму элементов массива можно получить, если разрешается выполнить любое количество описанных операций?
Помогите Ярославу.
Выходные данные
В единственную строку выведите ответ на задачу — максимальную сумму, которою может получить Ярослав.
Примечание
В первом примере ничего менять не нужно. Сумма элементов равна 150.
Во втором примере стоит поменять знак у первых двух элементов. Тогда получим сумму элементов равную 100.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
50 50 50
|
150
|
|
2
|
2
-1 -100 -1
|
100
|