Trạm thu tín hiệu từ vệ tinh nhận được dãy tín hiệu truyền về trái đất. Tín hiệu này sau khi được xử lý được biểu diễn thành một dãy n bit là dãy nhị phân, các bit được đánh số thứ tự từ 1 đến n. Một đoạn tín hiệu gồm các bit liên tiếp được gọi là tín hiệu chuẩn nếu số lượng bit 1 bằng số lượng bit 0. Hai đoạn bit được gọi là khác nhau nếu tồn tại một vị trí có thứ tự khác nhau trong tín hiệu ban đầu. Trước tiên cần xác định xem tín hiệu thu nhận được có bao nhiêu đoạn tín hiệu chuẩn.

Ví dụ: Dãy tín hiệu 1 0 1 0 1 1 có 6 đoạn tín hiệu chuẩn là:

Đoạn tín hiệu chuẩn thứ nhất từ vị trí 1 đến vị trí 2 là dãy tín hiệu (1, 0)

Đoạn tín hiệu chuẩn thứ nhất từ vị trí 1 đến vị trí 4 là dãy tín hiệu (1, 0, 1, 0)

Đoạn tín hiệu chuẩn thứ nhất từ vị trí 2 đến vị trí 3 là dãy tín hiệu (0, 1)

Đoạn tín hiệu chuẩn thứ nhất từ vị trí 2 đến vị trí 5 là dãy tín hiệu (0, 1, 0, 1)

Đoạn tín hiệu chuẩn thứ nhất từ vị trí 3 đến vị trí 4 là dãy tín hiệu (1, 0)

Đoạn tín hiệu chuẩn thứ nhất từ vị trí 4 đến vị trí 5 là dãy tín hiệu (0, 1)

Yêu cầu: Cho n là độ dài và dãy nhị phân A = (a₁, a₂, …, a_n) biểu diễn dãy tín hiệu thu nhận được. Hãy cho biết có bao nhiêu đoạn tín hiệu chuẩn.

Dữ liệu vào: Đọc từ file TINHIEU.INP gồm:

- Dòng đầu tiên chứa 1 số nguyên n ( n ≤ 10⁶)

- Dòng thứ 2 ghi n bit a₁, a₂, …, a_n

Dữ liệu ra: Ghi ra file TINHIEU.OUT gồm một số tự nhiên k là số lượng dãy tín hiệu chuẩn

Ví dụ: