Terrible maladie COWVID-19 se répand parmi les vaches du monde. Farmer John prend toutes précautions pour protéger le troupeau.

Grange longue étroite, $N$ stalles ($2 \leq N \leq 10^5$) en rang, occupées ou vides. Ayant lu l’importance de la distance, maximise $D$, où $D$ sépare les deux occupées les plus proches. Si3 et8, $D = 5$.

Deux nouvelles vaches dans stalles anciennement vides pour maximiser $D$. Aucune ancienne déplacée, seulement nouvelles assignées.

Entrée

Première ligne $N$, suivante chaîne01 de longueur $N$,0 vide1 occupée. Au moins deux0, place suffisante.

Sortie

Affichez maximum $D$ après placement optimal des deux, distance occupée minimale.

Exemples

Entrée 1

14
10001001000010

Sortie 1

2

Remarque

Possible 10x010010x0010, x nouvelles. $D = 2$, aucun $D$ supérieur possible.

Sous-tâches

• Tests2–6 satisfont $N\le 10$.
• Tests7–8 satisfont $N\le 100$.
• Tests9–11 satisfont $N \le 5000$.
• Tests12–15 sans autres contraintes.

Auteur du problème : Brian Dean