Cerința

Se dă un șir cu n elemente, numere întregi. Determinați secvența de elemente cu suma maximă.

Date de intrare

Fișierul de intrare secvsummax.in conține pe prima linie numărul n; urmează cele n elemente ale șirului, dispuse pe mai multe linii și separate prin spații.

Date de ieșire

Fișierul de ieșire secvsummax.out va conține pe prima linie numerele p și u, separate printr-un spațiu, reprezentând poziția de început și de sfârșit a secvenței determinate.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• elementele șirului vor avea cel mult 4 cifre și sunt numerotate de la 1 la n
• dacă șirul conține mai multe secvențe de suma maximă, se va determina cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă
• șirul va conține cel puțin un element pozitiv

Exemplu:

secvsummax.in

10
-4 1 -5 1 4 -2 2 3 -4 4

secvsummax.out

4 8

Explicație

Secvența 1 4 -2 2 3 are suma 8 și este suma maximă pentru toate secvențele care se pot forma.