Đề bài

Cho một xâu nhị phân S dài N. Một phép biến đổi: chọn một đoạn con liên tiếp và đảo tất cả bit trong đoạn (0 thành 1, 1 thành 0). Mục tiêu: biến S thành xâu trong đó số lượng ‘1’ ở mọi tiền tố không bao giờ ít hơn số ‘0’ (tức dạng “cân bằng” như dấu ngoặc), và tổng số ‘1’ bằng tổng số ‘0’. Tìm số phép biến đổi tối thiểu, hoặc in -1 nếu không thể.

Dữ liệu vào

\(N (1 \le N \le 2 * 10^5, N chẵn)\)

Xâu S (chỉ gồm ‘0’ và ‘1’)

Dữ liệu ra

Số phép biến đổi tối thiểu, hoặc -1.

Ví dụ