يشعر Farmer John بالطموح ويخطط لمحاولة أمر لا يبدو أنه ينجح تمامًا أبدًا: تصوير قطيع الأبقار كله.

لجعل الصورة جميلة، يريد أن تصطف الأبقار في صف واحد من الأقصر إلى الأطول. للأسف، بعد اصطفافها مباشرة، تخرج Bessie المشاغبة دائمًا من الصف وتدخل مجددًا في موضع آخر!

يريد Farmer John تبديل أزواج من الأبقار لإعادة القطيع كله إلى الترتيب الصحيح. ساعده على تحديد أقل عدد من التبديلات اللازمة.

الإدخال

يحتوي السطر الأول على $N$ ($2 \leq N \leq 100$). تصف الأسطر $N$ التالية أطوال الأبقار بترتيبها بعد حركة Bessie. طول كل بقرة عدد صحيح في النطاق $1 \ldots 1,000,000$. يمكن أن تتساوى أطوال الأبقار.

الإخراج

اطبع أقل عدد من تبديلات أزواج الأبقار للوصول إلى الترتيب الصحيح. ليس ضروريًا أن تكون البقرتان المتبادلتان متجاورتين.

أمثلة

الإدخال 1

6
2
4
7
7
9
3

الإخراج 1

3

ملاحظة

في هذا المثال، من الواضح أن Bessie هي البقرة ذات الطول 3. يعيد FJ الترتيب باستخدام التبديلات الثلاثة التالية:

2 4 7 7 9 3 - الترتيب الأصلي
2 4 7 7 3 9 - تبديل البقرتين الأخيرتين
2 4 3 7 7 9 - تبديل أول 7 مع 3
2 3 4 7 7 9 - تبديل 4 مع 3

مؤلف المسألة: Brian Dean