Cetatea Sucevei, construită de Petru Mușat în timpul zilelor glorioase ale Moldovei medievale de la sfârșitul secolului 14, și consolidată în al 15-lea secol de către Ștefan cel Mare, este cunoscută pentru faptul că nu a fost niciodată capturată de Imperiul Otoman. Sistemul medieval de fortificații al cetății a fost compus din diferite construcții (curți regale, mănăstiri cu pereți înalți și puncte strategice semnificative) concepute în scopuri defensive, care au fost înconjurate de ziduri înalte de piatră.

Reprezentăm un fragment din zidul cetății similar cu figura afișată mai jos. Blocurile de piatră care alcătuiesc peretele sunt ușor de identificat. Zidul este format din turnuri adiacente construite prin stratificarea blocurilor de piatră cubice identice. Astfel, pentru exemplul dat, zidul conține 10 turnuri, din care primul conține 5 blocuri, al doilea conține 4 blocuri, al treilea conține 7 blocuri, și așa mai departe. Rețineți că peretele nu are o înălțime constantă pe lungimea sa, deoarece unele dintre blocurile originale au fost distruse cu mult timp în urmă.

Restauratorii români au reușit să recupereze S blocuri de piatră și doresc să restaureze un fragment din zid care este cât mai mare posibil. Cu alte cuvinte, ei ar dori să repare o secvență continuă de turnuri prin adăugarea de blocuri în așa fel încât toate turnurile din secvență să aibă aceeași înălțime. Din motive istorice, înălțimea fragmentului restaurat nu trebuie să depășească cel mai înalt turn din fragment (înainte de restaurare).

Cerința

Dată fiind configurația zidului înainte de restaurare, compusă din N turnuri, indexate de la stânga la dreapta folosind numerele naturale cuprinse între 1 și N, și pentru fiecare turn având numărul de blocuri de piatră pe care îl conține, găsiți lungimea maximă a fragmentului de zid care poate fi restaurat, astfel încât restauratorii să folosească toate cele S blocuri de piatră recuperate în fragment. Lungimea fragmentului este definită ca numărul de turnuri conținute în acesta.

Date de intrare

Datele de intrare vor fi pe două linii. Prima linie conține două numere întregi pozitive separate prin spațiu: N și S (definite anterior). A doua linie conține N numere întregi pozitive separate printr-un spațiu, al i-lea dintre care înseamnă numărul de blocuri de piatră conținute în al i-lea turn al zidului.

Date de ieșire

Afișați o singură linie conținând două valori întregi separate printr-un spațiu: Lmax și Pos, cu următoarele
semnificații:

• Lmax – lungimea maximă a fragmentului de zid recuperat
• Pos – indexul celui mai din stânga turn din soluția optimă
• Vă garantăm că cel puțin un fragment poate fi restaurat utilizând toate cele S blocuri de piatră recuperate.

Dacă există mai multe fragmente cu aceeași lungime maximă, afișați poziția de pornire a fragmentului cu cea mai mare înălțime. Dacă ıncă există mai multe astfel de fragmente, afișați poziția de pornire a celui mai din stânga.

Restricții și precizări

• 1 ≤ N, S ≤ 200.000
• 1 ≤ numărul de blocuri din orice turn ≤ 10.000

Exemplu:

Intrare

11 7
5 4 7 6 4 7 6 8 7 5 1

Ieșire

5 6

Explicație

Observăm că există două fragmente cu lungime maximă (egală cu 5) care pot fi restaurate folosind exact S = 7 blocuri de piatră. Primul fragment este format din turnurile de la indexul 2 la indexul 6. Înălțimea sa după restaurare ar fi egală cu 7.

Al doilea fragment este format din turnurile de la indexul 6 la indexul 10. Înălțimea sa după restaurare ar fi egală cu 8. Deoarece după restaurare acest fragment ar fi mai înalt decât cel anterior, vom afișa indexul turnului său din stânga, adică 6.