Bartek เป็นโปรดิวเซอร์เพลงเทคโนชื่อดัง และขณะนี้เขากำลังปรับแต่งเพลงฮิตเพลงถัดไปของเขาให้สมบูรณ์แบบ เขาได้สร้างแทร็กที่ประกอบด้วย $n$ จังหวะ (บีต) ซึ่งมีหมายเลขกำกับเรียงกันตั้งแต่ $1$ ถึง $n$ หลังจากใช้เวลาหลายชั่วโมงในโปรแกรมตัดต่อเพลง เขากำลังจะส่งออกไฟล์ mp3 แต่สังเกตเห็นว่าจังหวะต่าง ๆ ปัจจุบันถูกจัดเรียงอยู่ในลำดับ $a_1, a_2, \dots, a_n$ Bartek ต้องการให้ลำดับของจังหวะเรียงจากน้อยไปมาก นั่นคือ $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$