Maksimali suma

Pradinių duomenų failas:

max.in  

Rezultatų failas:

max.out  

Laiko apribojimas:

2 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Parašykite programą, kuri duotoje sveikų skaičių sekoje rastų posekį su maksimalia suma.

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje įrašytas sveikas skaičius N – sekos ilgis (1 <= N <= 500000). Sekančiose N eilučių pateikti sekos nariai \(a_{i}\) (|\(a_{i}\)| <= 4000).

Rezultatai

Į rezultatų failą turi būti išvedami du sveikieji skaičiai I ir J (1 <= I <= J <= N), atskirti tarpo simboliu, tokie, kad sekos narių nuo I-ojo iki J-ojo suma būtų didžiausia galima. Jei yra keli posekiai su maksimalia suma, turite išvesti trumpiausią iš jų. Jei yra keli trumpiausi tokie posekiai, turite išvesti kairiausią iš jų.

Pavyzdys

3
-1
1
1

2 3

3
1
-3
1

1 1