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