Một căn bệnh mới khủng khiếp, COWVID-19, đã bắt đầu lây lan giữa các đàn bò trên toàn thế giới. Nông dân John đang cố gắng thực hiện nhiều biện pháp phòng ngừa nhất có thể để bảo vệ đàn bò của mình khỏi bị lây nhiễm.

Chuồng của Nông dân John là một tòa nhà dài và hẹp, gồm \(N\) ô chuồng xếp thành một hàng (\(2 \leq N \leq 10^5\)). Hiện tại, một số ô chuồng có bò ở, còn một số ô đang trống. Sau khi biết được tầm quan trọng của việc "giãn cách xã hội", Nông dân John muốn tối đa hóa \(D\), trong đó \(D\) là khoảng cách giữa hai ô chuồng có bò gần nhau nhất. Ví dụ, nếu ô chuồng 3 và ô chuồng 8 là hai ô có bò gần nhau nhất thì \(D = 5\).

Gần đây, hai con bò mới đã gia nhập đàn bò của Nông dân John, và ông cần quyết định xếp chúng vào những ô chuồng nào vốn đang trống. Hãy xác định cách xếp hai con bò mới sao cho giá trị \(D\) thu được vẫn lớn nhất có thể. Nông dân John không thể di chuyển bất kỳ con bò nào đang có sẵn; ông chỉ muốn xếp ô chuồng cho hai con bò mới.

Dữ liệu vào

Tệp socdist1.in:

Dòng đầu tiên chứa \(N\). Dòng tiếp theo chứa một xâu độ dài \(N\) gồm các ký tự 0 và 1, mô tả dãy ô chuồng trong chuồng bò. Ký tự 0 biểu thị ô chuồng trống và ký tự 1 biểu thị ô chuồng có bò. Xâu có ít nhất hai ký tự 0, vì vậy có đủ chỗ cho ít nhất hai con bò mới.

Dữ liệu ra

Tệp socdist1.out:

In ra giá trị \(D\) lớn nhất (khoảng cách nhỏ nhất giữa hai ô chuồng có bò) mà Nông dân John có thể đạt được sau khi thêm hai con bò mới theo cách tối ưu.

Phân nhóm

• Các test 2–6 thỏa mãn \(N \leq 10\).
• Các test 7–8 thỏa mãn \(N \leq 100\).
• Các test 9–11 thỏa mãn \(N \leq 5000\).
• Các test 12–15 không có ràng buộc bổ sung.

Ví dụ

14
10001001000010

2

Nguồn

USACO 2020 US Open Contest, Bronze — Social Distancing I

Tác giả bài: Brian Dean.