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