Archiwum zadań programistycznych WWSI

Masz daną różnicę o postaci:

a₁ - a₂ - a₃ - ... - a_n

Różnicę tę możesz raz zmodyfikować wstawiając do niej, w dowolnych miejscach, jedną albo dwie pary nawiasów. Możesz również pozostawić ją bez zmian. Twoim zadaniem jest obliczenie maksymalnego wyniku jaki można uzyskać.

Wejście

W pierwszej linii wejścia znajdują się jedna liczba całkowita n ∈ [1;1000] oznaczająca liczbę elementów różnicy. W kolejnej linii znajduje się n liczb całkowitych będących kolejnymi elementami różnicy. Każdy element różnicy mieści się w przedziale [-100;100].

Wyjście

Na wyjściu należy wypisać maksymalną wynik jaki możemy uzyskać, stosując albo i nie, opisane powyżej modyfikacje.

Przykład

Wejście

4
10 0 25 21

Wyjście

56

Wyjaśnienie do przykładu

56 możemy uzyskać wstawiając jedną parę nawiasów: 10 - (0 - 25 - 21)