يريد Farmer John تصوير قطيعه كله $N$ بقرة، $1 \le N \le 100,000$، مرقمة $1..N$، للتباهي لأصدقائه.

في يوم التصوير تركض الأبقار لتشكل صفًا بترتيب عشوائي، الموقع $i$ فيه $c_{i}$، $1 \le c_{i} \le N$. لديه أفكار للترتيب.

يعتقد FJ أن البقرة $i$ لا تقف إلا يسار $i+1$ لكل $i$، $1 \le i \le N-1$، و$N$ إلا يسار $1$. طبعًا لا بقرة يسار الأولى، الأقصى يسارًا.

جائعة للعشاء الموعود بعد الصورة فيريد الإسراع. لا تتبع التوجيه جيدًا، فلا يختار إلا زوجًا مجاورًا ويبادله مرة بالدقيقة. ما أسرع وقت لترتيب مقبول؟

مثال خمس أبقار أولًا:

     اليسار           اليمين
        3  5  4  2  1

يبادل الزوج الثاني أولًا:

        3  4  5  2 1

ثم الأقصى يمينًا:

        3  4  5  1  2

ليحصل على ترتيب مقبول بدقيقتين فقط من المبادلات.

الإدخال

• السطر $1$: عدد صحيح واحد $N$.

• الأسطر $2..N+1$: السطر $i+1$ رقم البقرة $i$، $c_{i}$.

الإخراج

• السطر $1$: أقل وقت بالدقائق لترتيب مناسب.

أمثلة

الإدخال 1

5
3
5
4
2
1

الإخراج 1

2

ملاحظة

مؤلف المسألة: Travis، 2010