المسألة

نلعب لعبة بوضع أحجار الغو البيضاء والسوداء في صف على طاولة. أولاً، نضع حجر غو عند الطرف الأيسر للطاولة. بعد ذلك، نضع حجر غو في الموضع رقم $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$)، نزيل أولاً الأحجار البيضاء الـ $3$ المتتالية ($\circ$) الموجودة في أقصى يمين الطاولة ونستبدلها بأحجار سوداء ($\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