Bạn lần lượt đặt \(n\) quân cờ vây trắng hoặc đen thành một hàng, từ trái sang phải. Khi đặt quân thứ \(i\), áp dụng quy tắc sau:

• Nếu \(i\) lẻ, giữ nguyên các quân đã có và đặt quân mới vào vị trí thứ \(i\) từ trái sang.
• Nếu \(i\) chẵn và quân mới cùng màu với quân ngoài cùng bên phải, giữ nguyên các quân đã có rồi đặt quân mới.
• Nếu \(i\) chẵn và hai màu khác nhau, thay toàn bộ đoạn quân cùng màu liên tiếp ở đầu bên phải bằng các quân cùng màu với quân mới, rồi đặt quân mới vào bên phải.

Ví dụ, nếu bảy quân hiện tại là ○○●●○○○ (trắng là ○, đen là ●), đặt quân thứ tám màu trắng sẽ được ○○●●○○○○; đặt quân thứ tám màu đen sẽ được ○○●●●●●●.

Biết màu của từng quân được đặt, hãy tính số quân trắng sau khi đặt đủ \(n\) quân.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa \(n\), với \(1 \le n \le 100000\). Dòng thứ \(i+1\) chứa \(c_i\): \(0\) nếu quân thứ \(i\) được đặt có màu trắng, \(1\) nếu có màu đen.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số quân trắng sau khi đặt đủ \(n\) quân.

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm. \(50\%\) số điểm ứng với dữ liệu có \(n \le 10000\).

Ví dụ

8
1
0
1
1
0
0
0
0

6

8
1
0
1
1
0
0
0
1

2