ברטק הוא מפיק מוזיקת טכנו מוכר, וכעת הוא מלטש את הלהיט הבא שלו. הוא יצר רצועה המורכבת מ-$n$ פעימות (beats), הממוספרות ברצף מ-$1$ עד $n$. לאחר שבילה שעות בתוכנת עריכת מוזיקה, הוא עמד לייצא את קובץ ה-mp3, אך הבחין שהפעימות מסודרות כעת בסדר $a_1, a_2, \dots, a_n$. ברטק צריך לקבל סדר עולה של פעימות, כלומר $1, 2, \dots, n$.

התוכנה מאפשרת שני סוגי פעולות:

• העברת הפעימה האחרונה לכל מיקום שהוא, למשל $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• העברת פעימה כלשהי להתחלה, למשל $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

מהו המספר המינימלי של פעולות הדרוש כדי לסדר את הפעימות בסדר עולה?

קלט

השורה הראשונה מכילה מספר שלם $n$ ($1 \le n \le 200\,000$), המציין את מספר הפעימות.

השורה השנייה מכילה $n$ מספרים שלמים שונים זה מזה $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), המייצגים את הסדר הנוכחי של הפעימות בתוכנה.

פלט

הדפיסו מספר שלם יחיד – המספר המינימלי של פעולות הנדרש.

דוגמאות

קלט 1

6
3 2 5 4 1 6

פלט 1

4

קלט 2

9
3 1 2 5 6 4 9 7 8

פלט 2

6

הערה

אנו מתחילים עם סדרת הפעימות $(3, 2, 5, 4, 1, 6)$. הנה דרך אחת להשיג את הסדר הרצוי בארבע פעולות:

• העברת הפעימה האחרונה שני מקומות שמאלה: $(3, 2, 5, \underline{6}, 4, 1)$.
• העברת פעימה $2$ להתחלה: $(\underline{2}, 3, 5, 6, 4, 1)$.
• העברת פעימה $1$ להתחלה: $(\underline{1}, 2, 3, 5, 6, 4)$.
• העברת הפעימה האחרונה שני מקומות שמאלה: $(1, 2, 3, \underline{4}, 5, 6)$.

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