Se consideră un şir a1, a2, ..., aN de valori binare şi de asemenea se consideră un număr natural K. În şir, unei singure secvenţe de K elemente i se va aplica o transformare astfel încât oricărei componente din această secvenţă i se inversează valoarea (adică 0 devine 1 şi 1 devine 0). De exemplu, considerând şirul 0 0 1 1 0 1 0 0 1 1 1 0 şi K=3, se poate obţine şirul 0 1 0 0 0 1 0 0 1 1 1 0 (dacă secvenţa de lungime 3 aleasă începe la poziţia 2), sau se poate obţine 0 0 1 1 0 0 1 1 1 1 1 0 (dacă secvenţa de lungime 3 aleasă începe la poziţia 6). Poziţia de început P a secvenţei de lungime K se va alege astfel încât întreaga secvenţă să fie în interiorul şirului, adică P <= N – K + 1.
Cerinţă
Scrieţi un program care determină o poziţie P din şir unde se aplică o transformare astfel încât în şirul rezultat să existe o secvenţă de lungime maximă formată doar cu valori de 1. Dacă există mai multe astfel de poziţii P, se alege aceea de indice minim.
Date de intrare
Fişierul de intrare maxbin.in conţine pe prima linie numerele naturale N şi K separate printr-un spaţiu. Pe linia a doua sunt N numere naturale (doar 0 şi 1) separate prin câte un spaţiu, reprezentând elementele şirului.
Date de ieşire
Fişierul de ieşire maxbin.out
va conţine pe prima alinie două numere naturale L şi P separate prin spaţiu. L va reprezenta lungimea maximă a unei secvenţe din şir formată doar din valori de 1 după aplicarea transformării, iar P reprezintă poziţia de început a secvenţei de lungime K unde se aplică transformarea.
Restricţii
1 <= K < N <= 100 000
Poziţia unde se poate aplica transformarea este în intervalul [1, N–K+1]
Prin secvenţă se înţelege o succesiune de elemente aflate pe poziţii alăturate din şir
Exemplu
maxbin.in
maxbin.out
Explicaţii
12 3
0 0 1 1 0 1 0 0 1 1 1 0
5 6
Se aplică transformarea de lungime 3 începând cu poziţia 6 şi se obţine şirul 0 0 1 1 0 0 1 1 1 1 1 0.
În acest şir lungimea maximă a unei secvenţe formată doar cu valori de 1 este 5.