مرض مخيف COWVID-19 ينتشر بين أبقار العالم. Farmer John يتخذ كل احتياط لحماية القطيع.

حظيرة طويلة ضيقة $N$ أماكن ($2 \leq N \leq 10^5$) بصف، مشغولة أو فارغة. قرأ أهمية التباعد فيعظم $D$؛ $D$ مسافة أقرب مكانين مشغولين. إن3 و8 الأقرب، $D = 5$.

بقرتان جديدتان في فارغين سابقًا لتعظيم $D$. لا يحرك القديمة، فقط يوزع الجديدتين.

الإدخال

أول سطر $N$، ثم سلسلة01 بطول $N$،0 فارغ1 مشغول. على الأقل صفران، مساحة كافية.

الإخراج

اطبع أكبر $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