הפרות בררניות מאוד לגבי שותפות לארוחה. הן נחלקו לקבוצות $1$ ו-$2$ ומתעקשות לסעוד יחד לפי סדר, $1$ בתחילת התור ו-$2$ בסופו. הבעיה מתחילה כשהן עומדות ליד האסם להיכנס לאזור ההאכלה.

כל פרה $i$ נושאת כרטיס עם $D_{i}$ ($1 \le D_{i} \le 2$), קבוצתה. כל $N$ הפרות ($1 \le N \le 30{,}000$) בתור, אך ברור שאינן מקובצות לפי הכרטיסים.

עבודת FJ קלה: ללכת לאורך התור, למחוק מספר ישן ולכתוב חדש לשינוי קבוצה. כך מתקבלים רצפים עולים כמו 112222 או 111122. לעיתים נותרת קבוצה אחת, למשל 1111 או 222.

FJ עצלן כמו אחרים. מהו מספר הכרטיסים המזערי לשינוי כדי לקבץ נכון? מותר לשנות מספרים בלבד, אסור לסדר מחדש את הפרות.

קלט

קראו מהקלט הסטנדרטי.

• שורה 1: שלם $N$.
• שורות $2,\ldots,N+1$: שורה $i+1$ מתארת העדפת פרה $i$ בשלם $D_{i}$.

פלט

כתבו לפלט הסטנדרטי.

• שורה 1: שלם, מספר הכרטיסים המזערי ש-Farmer John צריך לשנות לקיבוץ המתואר.

דוגמאות

קלט 1

7
2
1
1
1
2
2
1

פלט 1

2

הערה

שבע פרות; כולן מלבד שלוש מעדיפות כעת קבוצה $1$.

שנו את כרטיסי הפרה הראשונה והאחרונה.

קרדיט לבעיה: Ionescu Victor ו-Brian Dean, 2007