Laiko ribojimas: 2s

Atminties ribojimas: 16MB

Duomenų failas: max.in

Rezultatų failas: max.out

Jei norite pateikti savo sprendimą - prisijunkite.

Maksimali suma

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\\leN\\le500000). Sekančiose N eilučių pateikti sekos nariai a_i (|ai|\\le4000).

Rezultatai

Į rezultatų failą turi būti išvedami du sveikieji skaičiai I ir J (1\\leI\\leJ\\leN), 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