สับลำดับอาร์เรย์จำนวนเต็ม - Problem

กำหนดอาร์เรย์จำนวนเต็ม $A$ ขนาด $N$ มาให้ นิยามการดำเนินการสับลำดับดังต่อไปนี้

เริ่มต้น สร้างอาร์เรย์จำนวนเต็มว่าง $B$
จากนั้น ขณะที่ $A$ ยังไม่ว่าง ให้นำสมาชิกซ้ายสุดหรือขวาสุดของ $A$ ออก แล้วนำค่านั้นไปต่อท้ายทางขวาของ $B$
หาก $A$ ว่าง ให้แทน $A$ ด้วย $B$ แล้วหยุด

หากดำเนินการสับลำดับตามรูปข้างต้น ค่าในอาร์เรย์ $A$ จะเปลี่ยนดังนี้:

$$ (34,19,5,36,4,25,12,9)\to(9,34,19,12,25,4,5,36). $$

ให้ $A_i$ เป็นสมาชิกที่ $i$ ของอาร์เรย์ $A$ หากเงื่อนไข “ถ้า $1 \le i<j \le N$ แล้ว $A_i \le A_j$” เป็นจริง จะกล่าวว่าอาร์เรย์ $A$ เพิ่มแบบทางเดียว

จงเขียนโปรแกรมที่รับอาร์เรย์จำนวนเต็ม $A$ ขนาด $N$ แล้วคำนวณจำนวนการสับลำดับน้อยที่สุดที่ต้องใช้เพื่อทำให้อาร์เรย์ $A$ เพิ่มแบบทางเดียว

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มหนึ่งจำนวน $N$ ซึ่งเป็นจำนวนสมาชิกของอาร์เรย์ $A$ ($1 \le N \le 3\cdot 10^5$)

บรรทัดที่สองมีจำนวนเต็ม $N$ จำนวน $A_1,\ldots,A_N$ ซึ่งเป็นค่าเริ่มต้นของสมาชิกในอาร์เรย์ $A$ ($1 \le A_i \le 10^9$)

พิมพ์จำนวนการสับลำดับน้อยที่สุดที่ต้องใช้เพื่อทำให้อาร์เรย์ $A$ เพิ่มแบบทางเดียว

3
2 2 5

6
1 5 8 10 3 2

QOJ.ac