Hộp số

Có n chiếc hộp được đánh số theo thứ tự từ 1 đến n và xếp chúng theo một hàng ngang. Mỗi chiếc hộp có một trong hai giá trị 0 hoặc 1. Thực hiện một lần thay đổi giá trị của tất cả các hộp từ vị trí i, j ($1 \le i \le j \le n$) theo quy tắc “Những hộp có giá trị bằng 1 sẽ được thay đổi bằng 0 và ngược lại”, để sau khi thay đổi thì trong n chiếc hộp nhận được số chiếc hộp có giá trị bằng 1 là nhiều nhất.

Yêu cầu: Đếm số hộp có giá trị bằng 1 nhiều nhất sau khi thay đổi như trên.

Đọc từ tệp CAU3.INP có cấu trúc như sau:

• Dòng 1: Chứa số nguyên dương n ($0 < n \le 10^6$).
• Dòng 2: Chứa giá trị ban đầu của n chiếc hộp.

Ghi ra tệp CAU3.OUT kết quả theo yêu cầu bài toán.

• Có 30% số điểm của bài có $1 \le n \le 500$;
• Có 30% số điểm tiếp theo của bài có $500 < n \le 8000$;
• Có 40% số điểm còn lại của bài có $8000 < n \le 10^6$.