Se citesc un numar natural n si un vector cu n numere intregi, indexat de la 1. Determinati pozitiile de inceput si de sfarsit ale secventei de elemente consecutive cu suma maxima. Daca exista mai multe astfel de secvente, se considera prima gasita.
- Date de intrare
- Pe prima linie se afla numarul natural n. Pe a doua linie se afla n numere intregi, separate prin spatiu.
- Date de iesire
- Afiseaza pe o singura linie doua numere naturale separate prin spatiu: pozitia de inceput si pozitia de sfarsit (1-indexate) ale secventei gasite.
- Restrictii
- 1 <= n <= 1000, -10^9 <= a[i] <= 10^9
Exemple
Exemplul 1
Intrare
9 -2 1 -3 4 -1 2 1 -5 4
Iesire
4 7
Exemplul 2
Intrare
5 -1 -2 -3 -4 -5
Iesire
1 1