== include(page="template/taskheader" task_id="2sec") ==

Poveste si cerinta...

Singura avere a taranului Ion este formata din $N$ meri aliniati perfect intr-un sir, meri pe care Ion i-a numerotat de la $1$ la $N$. De la o vreme incoace Ion simte ca il lasa puterile si isi da seama ca va trebui sa dea o parte din meri spre folosinta celor $2$ fii ai lui. Dar Ion nu poate uita cum fiul cel mic i-a facut zilele amare de cand a crescut si hotaraste urmatoarele:
 
* fiecare dintre cei doi fii va primi o secventa de meri situati pe pozitii consecutive in sirul merilor
* numarul de meri din secventa primului fiu poate sa difere de numarul de meri din secventa celui de al doilea fiu, dar fiecare fiu va primi cel putin un mar
* fiul cel mic va primi meri cu numere de ordine strict mai mici decat fiul cel mare
* diferenta dintre profitul adus de merii fiului cel mare si profitul adus de merii fiului cel mic trebuie sa fie maxima
 
Profitul adus de un mar este calculat de Ion dupa formule complicate, perfectionate in decursul anilor.
 
h2. Cerinta
 
Scrieti un program care gaseste aceasta diferenta pentru Ion.

h2. Date de intrare

...

Pe prima linie a fisierului de intrare $2sec.in$ se afla un numarul natural $N$ reprezentand numarul de meri. Pe urmatoarea linie se gasesc $N$ numere intregi separate prin cate un spatiu, al $i$-lea numar reprezentand profitul adus de al $i$-lea mar.

h2. Date de iesire

...

Fisierul de iesire $2sec.out$ va contine o singura linie pe care se va afla diferenta maxima care poate fi obtinuta respectand cerintele lui Ion.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 1 001 000$
* $-127 ≤ profitul adus de un mar ≤ 127$

h2. Exemplu
table(example). |_. 2sec.in |_. 2sec.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 10
  8 -5 1 -3 7 -3 2 8 -3 1
| 21

|
h3. Explicatie

...

Fiul cel mic primeste merii cu numerele de ordine 2, 3, 4 iar fiul cel mare merii cu numerele de ordine 5, 6, 7, 8.

== include(page="template/taskfooter" task_id="2sec") ==

1763