מחלה איומה COWVID-19 מתפשטת בין פרות העולם. Farmer John נוקט כל אמצעי להגן מהדבקה.

רפת ארוכה צרה $N$ תאים ($2 \leq N \leq 10^5$) בשורה, תפוסים וריקים. קרא חשיבות ריחוק וממקסם $D$; $D$ מרחק שני תפוסים קרובים. אם3 ו־8, $D = 5$.

שתי חדשות לתאים שהיו ריקים למרב $D$. אי אפשר להזיז קיימות, רק להקצות לחדשות.

קלט

שורה ראשונה $N$, הבאה מחרוזת01 אורך $N$,0 ריק1 תפוס. לפחות שני0, די מקום.

פלט

הדפיסו מרב $D$ אחרי הוספת שתיים מיטבית, מרחק תפוסים הקרובים.

דוגמאות

קלט 1

14
10001001000010

פלט 1

2

הערה

אפשר 10x010010x0010, x חדשות. $D = 2$, גדול יותר $D$ בלתי אפשרי.

תתי־משימות

• בדיקות2–6 מקיימות $N\le 10$.
• בדיקות7–8 מקיימות $N\le 100$.
• בדיקות9–11 מקיימות $N \le 5000$.
• בדיקות12–15 ללא תנאים נוספים.

מחבר הבעיה: Brian Dean