Mari iubitori de munte, Mars şi Ştefan hotărăsc să meargă într-o excursie într-un lanţ muntos, format din N munţi. Aceşti munţi sunt situaţi unul după altul şi sunt dispuşi circular (al i-lea munte are ca vecini munţii i–1 şi i+1, şi al N-lea munte este lipit de primul şi de al N–1 lea). Sensul de deplasare este de la muntele 1 spre muntele 2.
Având deja o mare experienţă în domeniu, ei apreciază foarte exact timpul necesar (exprimat în ore) pentru escaladarea fiecărui munte.
Totuşi, cu fiecare munte escaladat, ei obosesc şi timpul de escaladare iniţial estimat va creşte. Astfel, după escaladarea muntelui de start, timpul de escaladare a a muntelui următor va creşte cu o oră. După escaladarea muntelui de start şi a următorului, timpul de escaladare a celui de al treilea munte va creşte cu două ore. Astfel, după escaladarea a i munţi, timpul necesar pentru escaladarea următorului munte va fi cu i ore mai mare decât timpul estimat iniţial.
Excursia poate porni de la poalele oricărui munte astfel că ei îşi pun problema de unde să înceapă excursia astfel încât la final, timpul maxim în care au escaladat un munte să fie minim.
Cerinţă
Sa se determine muntele de unde cei doi încep excursia şi timpul maxim pentru a urca un munte în cadrul excursiei, timp minim având în vedere celelalte variante de start.
Date de intrare
Fişierul de intrare munte2.in conţine pe prima linie un număr natural N reprezentând numărul de munţi. A doua linie va conţine un şir de N numere naturale, separate prin câte un spaţiu. Al i-lea număr de pe linie reprezintă numărul de ore necesare pentru escaladarea muntelui i din lanţ, neluând în calcul şi oboseala.
Date de ieşire
Fişierul de ieşire munte2.out va conţine pe prima linie două numere naturale separate printr-un spaţiu: muntele de unde cei doi încep excursia şi timpul maxim pentru a urca un munte în cadrul excursiei, timp minim având în vedere celelalte variante de start.
Restricţii
1 <= N <= 1 000 000
Exemple
munte2.in
munte2.out
Explicaţii
4
5 9 10 3
2 11
Pornim excursia de la muntele 2. Timpii de escaladare sunt: 9, 10 + 1, 3 + 2, 5 + 3 cu maximul 11. Orice altă alegere a muntelui de start conduce la timpi maximi mai mari.