โจทย์ปัญหา

เราเล่นเกมโดยการนำเม็ดหมากล้อมสีขาวและสีดำมาวางเรียงบนโต๊ะ ขั้นแรกวางเม็ดหมากล้อมที่ปลายสุดด้านซ้ายของโต๊ะ ถัดไปวางเม็ดหมากล้อมในตำแหน่งที่ $2$ จากด้านซ้าย ทำซ้ำเช่นนี้ $n$ ครั้งเพื่อเรียงเม็ดหมากล้อม $n$ เม็ดเป็นแถวแนวนอนแถวเดียว อย่างไรก็ตาม เมื่อจะวางเม็ดหมากล้อมเม็ดใหม่ลำดับที่ $i$ จะทำการแทนที่เม็ดหมากล้อมบนโต๊ะตามกฎต่อไปนี้:

• กรณีที่ $i$ เป็นจำนวนคี่: ไม่ต้องแทนที่เม็ดหมากล้อมที่วางอยู่แล้วบนโต๊ะ โดยวางเม็ดหมากล้อมเม็ดใหม่ลงในตำแหน่งที่ $i$ จากด้านซ้าย
• กรณีที่ $i$ เป็นจำนวนคู่: หากสีของเม็ดหมากล้อมเม็ดใหม่ที่จะวางในตำแหน่งที่ $i$ จากด้านซ้ายเหมือนกับสีของเม็ดหมากล้อมที่อยู่ขวาสุดบนโต๊ะ ก็ไม่ต้องแทนที่เม็ดหมากล้อมบนโต๊ะ โดยวางเม็ดหมากล้อมเม็ดใหม่ลงในตำแหน่งที่ $i$ จากด้านซ้าย มิฉะนั้น กล่าวคือหากสีของเม็ดหมากล้อมเม็ดใหม่ที่จะวางในตำแหน่งที่ $i$ จากด้านซ้ายต่างจากสีของเม็ดหมากล้อมที่อยู่ขวาสุดบนโต๊ะ ขั้นแรกให้นำเม็ดหมากล้อมสีเดียวกันที่เรียงติดกันอยู่ทางปลายด้านขวาของโต๊ะออกทั้งหมด แล้วแทนที่ด้วยเม็ดหมากล้อมที่มีสีเดียวกันกับเม็ดหมากล้อมลำดับที่ $i$ จากนั้นจึงวางเม็ดหมากล้อมลำดับที่ $i$ ที่ปลายสุดด้านขวาของโต๊ะ

ตัวอย่างเช่น สมมติว่าเมื่อวางเม็ดหมากล้อม $7$ เม็ดแรกเสร็จแล้ว มีลักษณะดังนี้:

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

(โดยที่ $\circ$ แทนเม็ดหมากล้อมสีขาว และ $\bullet$ แทนเม็ดหมากล้อมสีดำ)

• หากเม็ดหมากล้อมลำดับที่ $8$ เป็นสีขาว ($\circ$) เนื่องจากมีสีเดียวกับเม็ดหมากล้อมขวาสุด จึงวางลงไปตามปกติ ดังนั้น เม็ดหมากล้อมบนโต๊ะจึงกลายเป็น:

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

• หากเม็ดหมากล้อมลำดับที่ $8$ เป็นสีดำ ($\bullet$) เนื่องจากมีสีต่างจากเม็ดหมากล้อมขวาสุด ($\circ$) ขั้นแรกจึงนำเม็ดหมากล้อมสีขาว ($\circ$) ที่เรียงติดกัน $3$ เม็ดที่ปลายด้านขวาของโต๊ะออก แล้วแทนที่ด้วยเม็ดหมากล้อมสีดำ ($\bullet$) จากนั้นวางเม็ดหมากล้อมลำดับที่ $8$ ที่ปลายด้านขวา ดังนั้น เม็ดหมากล้อมบนโต๊ะจึงกลายเป็น:

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

เมื่อกำหนดลำดับของเม็ดหมากล้อมที่จะวางเป็นข้อมูลนำเข้า จงเขียนโปรแกรมเพื่อหาจำนวนเม็ดหมากล้อมสีขาวที่วางอยู่บนโต๊ะหลังจากเรียงเม็ดหมากล้อมครบทั้ง $n$ เม็ดแล้ว

ข้อมูลนำเข้า

บรรทัดที่ $1$ มีจำนวนเต็มบวก $n$ ($1 \le n \le 100\,000$) เขียนอยู่ ตั้งแตบรรทัดที่ $2$ เป็นต้นไป ในบรรทัดที่ $i+1$ ($1 \le i \le n$) มีจำนวนเต็ม $c_{i}$ ที่แทนสีของเม็ดหมากล้อมที่จะวางในลำดับที่ $i$ เขียนอยู่ โดยถ้า $c_{i}$ เป็น $0$ จะแทนว่าสีของเม็ดหมากล้อมที่จะวางในลำดับที่ $i$ เป็นสีขาว และถ้าเป็น $1$ จะแทนว่าสีของเม็ดหมากล้อมที่จะวางในลำดับที่ $i$ เป็นสีดำ

ในข้อมูลที่ใช้ตรวจให้คะแนน สำหรับส่วนที่มีคะแนนคิดเป็น $50\%$ ของคะแนนทั้งหมด จะสอดคล้องกับ $n \le 10\,000$

ข้อมูลส่งออก

พิมพ์ $1$ บรรทัดที่ประกอบด้วยจำนวนเม็ดหมากล้อมสีขาวที่วางอยู่บนโต๊ะหลังจากเรียงเม็ดหมากล้อมครบ $n$ เม็ดแล้วเท่านั้น

ตัวอย่างข้อมูลนำเข้าและส่งออก

ตัวอย่างข้อมูลนำเข้า 1

8
1
0
1
1
0
0
0
0

ตัวอย่างข้อมูลส่งออก 1

6

ตัวอย่างข้อมูลนำเข้า 2

8
1
0
1
1
0
0
0
1

ตัวอย่างข้อมูลส่งออก 2

2