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

Pradiniai duomenys Rezultatai
3
-1
1
1
2 3
3
1
-3
1
1 1