Bệnh đáng sợ COWVID-19 lan giữa bò thế giới. Farmer John phòng tối đa bảo vệ đàn.

Chuồng dài hẹp $N$ ô ($2 \leq N \leq 10^5$) một hàng, có bò hoặc trống. Đọc tầm quan trọng giãn cách, tối đa $D$; $D$ khoảng cách hai ô có bò gần nhất. Nếu3 và8 gần nhất, $D = 5$.

Hai bò mới vào ô trước trống để tối đa $D$. Không chuyển bò cũ, chỉ xếp mới.

Dữ liệu vào

Dòng đầu $N$, sau chuỗi01 dài $N$,0 trống1 có bò. Ít nhất hai0, đủ chỗ.

Dữ liệu ra

In lớn nhất $D$ sau xếp hai tối ưu, khoảng cách ô có bò gần nhất.

Ví dụ

Dữ liệu vào 1

14
10001001000010

Dữ liệu ra 1

2

Ghi chú

Có thể 10x010010x0010, x bò mới. $D = 2$, lớn hơn $D$ không thể.

Nhiệm vụ con

• Kiểm thử2–6 thỏa $N\le 10$.
• Kiểm thử7–8 thỏa $N\le 100$.
• Kiểm thử9–11 thỏa $N \le 5000$.
• Kiểm thử12–15 không thêm ràng buộc.

Tác giả bài toán: Brian Dean