الأبقار متطلبة جدًا بشأن رفيقات العشاء. قسمت نفسها لمجموعتين $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