Cho \(n\) đồng xu được đánh số từ 1 đến \(n\), đặt trên một hàng dài theo thứ tự từ trái sang phải. Đồng xu thứ \(i\) có mặt \(x_{i}\) ngửa lên (\(x_{i}\ = 0\) là mặt hình, \(x_{i}\ = \ 1\) là mặt số, \(1 \leq i \leq n\)). Bạn phải duyệt và xử lý các đồng xu từ 1 đến \(n\) theo qui tắc như sau: Khi duyệt đến đồng xu thứ \(i\)

• Với \(i\) lẻ: không thay đổi trạng thái các đồng xu.

• Với \(i\) chẵn: Nếu đồng xu thứ \(i\) có cùng mặt \(x\) của đồng xu thứ \(i - 1\) (\(x\): mặt hình hay mặt số) thì không thay đổi trạng thái các đồng xu, trong trường hợp ngược lại thì bạn phải lật mặt liên tiếp các đồng xu cùng mặt \(x\) bắt đầu từ đồng xu thứ \(i - 1\) trở về trước.

Ví dụ trên dãy đã duyệt được 7 đồng xu: 0 0 1 1 0 0 0

• Nếu đồng xu thứ 8 có mặt hình ta sẽ có dãy chứa 6 mặt hình: 0 0 1 1 0 0 0 0

• Nếu đồng xu thứ 8 có mặt số ta sẽ chỉ có 2 mặt hình trong dãy: 0 0 1 1 1 1 1 1

Yêu cầu: Cho số \(n\) và \(n\) trạng thái ngửa mặt của các đồng xu. Hãy xác định số lượng các đồng xu mặt hình trong dãy sau khi duyệt hết \(n\) đồng xu.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên \(n\).

• Dòng thứ 2 có \(n\) số nguyên \(x_{i}\) mỗi số cách nhau một khoảng trắng.

Kết quả: một số nguyên là số lượng đồng xu ngửa mặt hình trong dãy.

Ví dụ:

Ràng buộc:

• 50% số test tương ứng với \(n \leq \ 10^{3}\)

• 50% số test tương ứng với \(n \leq \ 10^{6}\)