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.

Cerinta
Scrieti un program care gaseste aceasta diferenta pentru Ion.

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.

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.

Restrictii

1 < N < 1001001
-128 < profitul adus de un mar < 128

Exemplu

Fechete Dan Ionut
Universitatea Bucuresti, Facultatea de Matematica si Informatica
f.dan.ionut@gmail.com