== include(page="template/taskheader" task_id="ssm") ==

Poveste şi cerinţă...

Se dă un şir $S[] = (s{~1~}, s{~2~}, .., s{~N~})$ de lungime $N$. O subsecvenţă a şirului este de forma $(s{~i~}, s{~i+1~}, ..., s{~j~})$, cu $1 ≤ i ≤ j ≤ N$. Suma subsecvenţei este $s{~i~} + s{~i+1~} + ..., s{~j~}$.
 
h2. Cerinţă
 
Se cere să se determine subsecvenţa de sumă maximă.

h2. Date de intrare

Fişierul de intrare $ssm.in$ ...

Fişierul de intrare $ssm.in$ conţine pe prima linie un număr natural $N$, reprezentând lungimea şirului. Pe următoarea linie se găsesc $N$ numere întregi separate printr-un spaţiu, reprezentând în ordine elementele şirului.

h2. Date de ieşire

În fişierul de ieşire $ssm.out$ ...

În fişierul de ieşire $ssm.out$ se vor tipări trei numere în această ordine: suma subsecvenţei de sumă maximă, indicele de început şi indicele de sfârşit.

h2. Restricţii

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

* $1 ≤ N ≤ 5 000 000$
* $|S{~i~}| ≤ 1 000$
* Pentru $20%$ dintre teste: $1 ≤ N ≤ 1 000$.
* Pentru încă $20%$: $5 000 ≤ N ≤ 50 000$.
* Pentru restul de $60%$: $100 000 ≤ N ≤ 5 000 000$.
* Dacă există mai mult subsecvenţe candidate la soluţie, atunci se va tipări cea cu indicele de început cel mai mic, iar în caz de egalitate cea mai scurtă.
* Se garantează că toate rezultatele intermediare şi cel final vor putea fi reprezentate pe întregi cu semn pe $32$ de biţi.

h2. Exemplu
table(example). |_. ssm.in |_. ssm.out |

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

| 7
5 -6 3 4 -2 3 -3
| 8 3 6

|
h3. Explicaţie