בעיה

אנו משחקים משחק שבו מסדרים אבני גו לבנות ושחורות על שולחן. תחילה מניחים אבן גו בקצה השמאלי של השולחן. לאחר מכן מניחים אבן גו במיקום ה-$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