Suzi și Costel

Suzi și Costel participă la un concurs pluridisciplinar pe echipe. La secțiunea de informatică, aceștia au primit un set $A$ cu $N$ numere întregi. Fiecare poate să aleagă doar o singură secvență din șir. În plus, aceste secvențe nu pot să se suprapună sau să fie vide.

Aceștia vă roagă să găsiți valoarea maximă a disimilarității dintre oricare două secvențe nevide, care nu se suprapun, din setul de $N$ numere întregi $A$.

Valoarea disimilitudinii este definită ca diferența absolută a sumelor elementelor celor două secvențe.

Date de intrare

Pe prima linie se găsește un număr întreg $N$, având semnificația descrisă în enunț.
Pe a doua linie se găsesc $N$ numere întregi, acestea fiind valorile din șirul $A$.

Date de ieșire

Să se afișeze un singur număr întreg, aceasta fiind valoarea maximă a disimilarității dintre oricare două secvențe nevide și care nu se suprapun din șirul $A$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$;
• $-10^9 \leq A_i \leq 10^9$, cu $i=\overline{0,N-1}$.

Exemplu

stdin

5
7 3 -7 8 12 

stdout

27

Explicație

În exemplul de mai sus, valoarea maximă a disimilarității poate fi obținută prin selectarea secvenței $[-7]$ și a secvenței $[8, 12]$. Valoarea disimilarității este $|(-7) - (8 + 12)| = |-7 - 20| = |-27| = 27$.