Počet bodov:
Popis:  7b
Program:  8b

Určite poznáte krtka Peťka. Celé dni vyspáva v svojej podzemnej nore a zobudí sa iba vtedy, keď sa ide najesť. Našťastie, býva priamo pod jabloňovým sadom, stačí sa mu teda vykopať hore, pojesť čo najviac jabĺk a vrátiť sa do svojho pelechu, aby tam pokračoval vo svojej obľúbenej činnosti.

Jabloňový sad je vlastne rad \(n\) stromov, pod ktorými sú napadané jablká. Peťko si vždy vyberie nejaký súvislý úsek jabloní, vykope sa na jeho začiatku, potom prejde až k jeho koncu a zakope sa späť pod zem. Popritom zje všetky jablká, na ktoré narazí.

Niektoré jablká však padli už veľmi dávno a preto zhnili. Peťko je však takmer úplne slepý a preto nevie rozlíšiť zhnité jablko od toho zdravého. Časom sa už zmieril s tým, že na to, aby sa dobre najedol, musí zjesť aj nejaké hnilé jablká. Snaží sa však, aby rozdiel medzi počtom zdravých a zhnitých jabĺk, ktoré zje, bol čo najväčší.

Po tomto príbehu je vám určite ľúto chudáka Peťka, s jeho ťažkým životným štýlom. Môžete mu však pomôcť. Stačí ak mu poradíte, ktorý úsek jabloní si má vybrať, aby sa čo najlepšie najedol.

Úloha

Na vstupe dostanete popis jabloňového sadu ako postupnosť celých čísel. Pre každý strom budete vedieť, aký je rozdiel počtu zdravých a hnilých jabĺk pod týmto stromom. Keďže Peťko zje pod každým stromom všetky jablká, toto je naozaj jediná informácia, ktorú potrebujete.

Zistite, ktorý zo súvislých úsekov si má Peťko vybrať, aby bol rozdiel medzi počtom zdravých a zhnitých jabĺk, ktoré zje, najväčší možný.

Vstup

Prvý riadok vstupu obsahuje prirodzené číslo \(n\) (\(1 \leq n \leq 1\,000\,000\)) udávajúce počet stromov v sade.

Druhý riadok obsahuje \(n\) celých čísel \(p_i\) (\(-1\,000\,000\,000 \leq p_i \leq 1\,000\,000\,000\)) – rozdiely dobrých a zlých jabĺk pod jednotlivými stromami.

Výstup

Vypíšte jeden riadok a v ňom dve čísla \(a\), \(b\). Nech \(a\) (\(1 \leq a \leq n\)) je strom, pri ktorom sa má Peťko vykopať a \(b\) je počet stromov (vrátane stromu \(a\)), ktoré má prejsť smerom doprava. Ak existuje viacero riešení, vypíše ľubovoľné z nich.

Príklady

Input:

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

Output:

4 5

Krtkovi sa oplatí vykopať pri strome číslo 4 s počtom jabĺk 1, spapať potom 2, 3, 4 a 5 jabĺk pri nasledujúcich stromoch. Neoplatí sa mu ísť ďalej, takže sa zakope pri strome číslo 8.

Input:

5
-2 10 2 -3 4

Output:

2 4

Input:

3
1000000000 1000000000 1000000000

Output:

1 3

Dajte si pozor na veľkosť premennej, v ktorej si budete pamätať súčet!

Input:

5
-47 -42 -17 -13 -12

Output:

3 0

Môžte si všimnút že správnych riešení je 5.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.