Đề bài

Ta chơi một trò chơi bằng cách xếp các quân cờ vây trắng và đen lên mặt bàn. Đầu tiên, đặt một quân cờ vây ở đầu bên trái của bàn. Tiếp theo, đặt một quân cờ vây ở vị trí thứ $2$ tính từ bên trái. Lặp lại việc này $n$ lần để xếp $n$ quân cờ vây thành một hàng ngang. Tuy nhiên, khi đặt quân cờ vây mới thứ $i$, ta thay thế các quân cờ vây trên bàn theo quy tắc sau:

• Khi $i$ là số lẻ: Không thay thế các quân cờ vây đã có trên bàn, đặt quân cờ vây mới vào vị trí thứ $i$ tính từ bên trái.
• Khi $i$ là số chẵn: Nếu màu của quân cờ vây mới đặt ở vị trí thứ $i$ tính từ bên trái giống với màu của quân cờ vây ngoài cùng bên phải trên bàn thì không thay thế các quân cờ vây trên bàn, đặt quân cờ vây mới vào vị trí thứ $i$ tính từ bên trái. Ngược lại, tức là nếu màu của quân cờ vây mới đặt ở vị trí thứ $i$ tính từ bên trái khác với màu của quân cờ vây ngoài cùng bên phải trên bàn, trước hết lấy ra tất cả các quân cờ vây cùng màu liên tiếp ở đầu bên phải trên bàn và thay thế bằng các quân cờ vây có cùng màu với quân cờ vây thứ $i$. Sau đó đặt quân cờ vây thứ $i$ vào đầu bên phải của bàn.

Ví dụ, giả sử tại thời điểm đã đặt $7$ quân cờ vây đầu tiên, trạng thái là:

$$\circ \circ \bullet \bullet \circ \circ \circ$$

(trong đó $\circ$ biểu thị quân cờ vây trắng, $\bullet$ biểu thị quân cờ vây đen).

• Nếu quân cờ vây thứ $8$ là màu trắng ($\circ$), vì nó cùng màu với quân cờ vây ngoài cùng bên phải nên ta đặt nguyên như vậy. Do đó, các quân cờ vây trên bàn trở thành:

$$\circ \circ \bullet \bullet \circ \circ \circ \circ$$

• Nếu quân cờ vây thứ $8$ là màu đen ($\bullet$), vì nó khác màu với quân cờ vây ngoài cùng bên phải ($\circ$), trước hết ta lấy ra $3$ quân cờ vây trắng ($\circ$) liên tiếp ở đầu bên phải của bàn và thay thế bằng các quân cờ vây đen ($\bullet$). Sau đó đặt quân cờ vây thứ $8$ vào đầu bên phải. Do đó, các quân cờ vây trên bàn trở thành:

$$\circ \circ \bullet \bullet \bullet \bullet \bullet \bullet$$

Khi được cho thứ tự các quân cờ vây sẽ đặt làm dữ liệu vào, hãy viết chương trình tìm số lượng quân cờ vây trắng nằm trên bàn sau khi đã xếp xong $n$ quân cờ vây.

Dữ liệu vào

Ở dòng thứ $1$ ghi số nguyên dương $n$ ($1 \le n \le 100\,000$). Ở dòng thứ $i+1$ ($1 \le i \le n$) kể từ dòng thứ $2$ trở đi ghi số nguyên $c_{i}$ biểu thị màu của quân cờ vây đặt ở lượt thứ $i$, trong đó $c_{i}$ bằng $0$ biểu thị quân cờ vây thứ $i$ có màu trắng, bằng $1$ biểu thị quân cờ vây thứ $i$ có màu đen.

Trong dữ liệu chấm bài, $50\%$ số điểm thỏa mãn $n \le 10\,000$.

Dữ liệu ra

In ra $1$ dòng duy nhất chỉ chứa số lượng quân cờ vây trắng nằm trên bàn sau khi đã xếp xong $n$ quân cờ vây.

Ví dụ dữ liệu vào và dữ liệu ra

Dữ liệu vào mẫu 1

8
1
0
1
1
0
0
0
0

Dữ liệu ra mẫu 1

6

Dữ liệu vào mẫu 2

8
1
0
1
1
0
0
0
1

Dữ liệu ra mẫu 2

2