E. Шведские герои
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Играя в очередную стратегическую игру, Мэнс набрал $$$n$$$ Шведских героев, силы которых можно представить в виде массива $$$a$$$.

К сожалению, не все эти могущественные герои были созданы настолько способными, насколько он хотел, так что он решил что-то с этим сделать. Для достижения своей цели он может выбрать двух последовательных героев, с силами $$$a_i$$$ и $$$a_{i+1}$$$, удалить их и вставить обратно в ту же позицию героя с силой $$$-(a_i+a_{i+1})$$$.

Например, если элементы нашего массива — $$$[5, 6, 7, 8]$$$, то мы можем выбрать $$$6$$$ и $$$7$$$ и получить $$$[5, -(6+7), 8] = [5, -13, 8]$$$.

После того, как он выполнит эту операцию $$$n-1$$$ раз, у него останется только один герой. Мэнс хочет, чтобы его сила была как можно больше. Какой наибольшей силы этого героя он может достичь?

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 200000$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива.

Выходные данные

Выведите наибольшую возможную силу, которую он может получить после $$$n-1$$$ операций.

Примеры
Входные данные
4
5 6 7 8
Выходные данные
26
Входные данные
5
4 -5 9 -2 1
Выходные данные
15
Примечание

Оптимальный список операций для первого примера:

$$$[5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26]$$$.