

		PLATI SI INCASARI
	       -------------------

Fisier sursa: CASIER.PAS, CASIER.C sau CASIER.CPP

	Casierul unei firme trebuie sa parcurga zilnic un traseu liniar
prin cele N magazine ale sale. Magazinele sunt numerotate de la 1 la N
si se parcurg zilnic in ordinea numerelor lor de ordine, incepand cu
primul magazin si treminand cu al N-lea (Evident casierul va trece doar
o singura data prin fiecare magazin). Scopul parcurgerii acestui traseu
este efectuarea unor plati, respectiv a unor incasari. Se stie ca exis-
ta CEL PUTIN UN magazin de unde casierul va incasa bani. De asemenea se
cunosc sumele care trebuie platite, respectiv incasate.
	Intr-o zi, patronul nu are bani pentru plati si cere casierului
sa aleaga 2 magazine m(i) si m(j) de pe traseu, astfel incat parcurgand
traseul incepand cu m(i) si incheindu-l cu m(j), incasarile sa reprezin-
te suma MAXIMA posibila de adus inapoi la firma. Casierul trebuie sa in-
tre in toate magazinele aflate pe traseul ales, chiar daca in unele tre-
buie sa efectueze plati. In plus, pentru a nu crea suspiciuni printre
angajatii magazinelor, patronul doreste sa fie vizitate cat mai MULTE
magazine.

Cerinta
	Scrieti un program care determina suma MAXIMA posibila de incasat
din magazinele firmei. De asemenea, determinati secventa cea mai LUNGA
de magazine care permite obtinerea acestei sume. Daca aceeasi suma ma-
xima se poate obtine pentru mai multe alegeri diferite, vizitand ace-
lasi numar maxim de magazine, atunci in fisierul de iesire se va scrie
una singura, si anume cea care incepe de la magazinul cu numarul de or-
dine cel mai MIC.


Date de intrare

Fisier de intrare: CASIER.IN

Linia 1: N
- numar natural nenul, reprezentand numarul magazinelor de pe traseul
  initial

Linia 2: Suma(1) Suma(2) .. Suma(N)
- N numere intregi, separate prin cate un spatiu, reprezentand sumele pe
  care casierul ar trebui sa le plateasca sau sa le incaseze in/din cele
  N magazine; numerele pozitive reprezinta sume care se vor incasa, iar
  numerele negative corespund sumelor care se vor plati.


Restrictii
- 1<= N <= 100.000
- -1000<= Suma(i) <= 1000   i = 1,2,..,N
- 1<= SumaMax <= 100.000.000


Exemplu

CASIER.IN			CASIER.OUT
10				13
2 3 -6 5 -6 6 7 -2 2 -1		6 9

Timp maxim de executare/test: 1 secunda
