Играя в очередную стратегическую игру, Мэнс набрал \(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\) раз, у него останется только один герой. Мэнс хочет, чтобы его сила была как можно больше. Какой наибольшей силы этого героя он может достичь?
Примечание
Оптимальный список операций для первого примера:
\([5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26]\).