Truy Vết Tiếp Xúc 2

Nông dân John có $N$ con bò xếp thành một hàng. Một số con bò ban đầu bị nhiễm bệnh. Mỗi đêm, một con bò bị nhiễm bệnh sẽ lây lan bệnh sang con bò liền kề bên trái và bên phải (nếu tồn tại). Một khi con bò đã bị nhiễm, nó sẽ luôn bị nhiễm.

Cho trạng thái cuối cùng của các con bò sau một số đêm, hãy xác định số lượng tối thiểu con bò có thể đã bị nhiễm bệnh ban đầu.

Dữ liệu vào

• Dòng $1$: Số nguyên $N$ ($1\le N\le 3·{10}^5$).
• Dòng $2$: Xâu $N$ ký tự gồm các chữ số $0$ và $1$, trong đó $1$ biểu thị con bò bị nhiễm bệnh và $0$ biểu thị con bò không bị nhiễm.

Dữ liệu ra

In ra một số nguyên duy nhất -- số lượng tối thiểu con bò ban đầu bị nhiễm bệnh.

Ràng buộc

• Các test $3$-$7$: $N\le 1000$.
• Các test $8$-$12$: Không có ràng buộc thêm.

Ví dụ