คุณได้รับการเรียงสับเปลี่ยน $P = (P_1, P_2, \dots, P_N)$ ของ $(1, 2, \dots, N)$
สำหรับลำดับของจำนวนเต็มบวก $T = (T_1, T_2, \dots, T_{N-1})$ ที่มีความยาว $N - 1$ ค่า $f(T)$ ถูกนิยามให้เป็นค่าที่ส่งกลับของกระบวนการต่อไปนี้
กระบวนการ $f(T)$
- $t \leftarrow 0$
- ในขณะที่ $P$ ยังไม่ได้เรียงลำดับจากน้อยไปมาก:
- (a) $t \leftarrow t + 1$
- (b) ให้ $S = (s_1, s_2, \dots, s_k)$ เป็นลำดับของดัชนีทั้งหมด $i \in \{1, \dots, N - 1\}$ ที่ทำให้ $T_i \le t$ โดยเรียงจากน้อยไปมาก ($s_1 < s_2 < \dots < s_k$)
- (c) สำหรับ $j = 1$ ถึง $k$:
- ให้ $i \leftarrow s_j$ จากนั้นสลับค่า $P_i$ และ $P_{i+1}$
- (d) ถ้า $t \ge 10^{100}$ ให้ส่งกลับค่า $10^{100}$
- ส่งกลับค่า $t$
จงหาค่าที่น้อยที่สุดที่เป็นไปได้ของ $f(T)$ จากทุกลำดับของจำนวนเต็มบวก $T$ รับประกันว่ามีลำดับ $T$ ที่ทำให้ $f(T) < 10^{100}$
ข้อมูลนำเข้า
ข้อมูลนำเข้าจะให้มาในรูปแบบต่อไปนี้:
N P_1 P_2 ... P_N
- ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ สำหรับ $i \neq j$
ข้อมูลส่งออก
แสดงคำตอบ
ตัวอย่าง 1
4
4 2 1 3
2
ตัวอย่าง 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
หมายเหตุ
ในตัวอย่างแรก ให้ $T = (2, 1, 2)$ ที่ $t = 1$ เมื่อ $S = (2)$ ลำดับ $P$ จะกลายเป็น $(4, 1, 2, 3)$ ที่ $t = 2$ เมื่อ $S = (1, 2, 3)$ การสลับตามลำดับจะเปลี่ยน $P$ เป็น $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$ ดังนั้น $f(T) = 2$ เนื่องจากไม่มี $T$ ใดที่ทำให้ได้ $f(T) < 2$ คำตอบจึงเป็น $2$