Bạn được cho một hoán vị $P = (P_1, P_2, \dots, P_N)$ của $(1, 2, \dots, N)$.
Đối với một dãy số nguyên dương $T = (T_1, T_2, \dots, T_{N-1})$ có độ dài $N - 1$, giá trị $f(T)$ được định nghĩa là giá trị trả về của thủ tục sau:
Thủ tục $f(T)$
- $t \leftarrow 0$.
- Trong khi $P$ chưa được sắp xếp theo thứ tự tăng dần:
- (a) $t \leftarrow t + 1$.
- (b) Gọi $S = (s_1, s_2, \dots, s_k)$ là dãy tất cả các chỉ số $i \in \{1, \dots, N - 1\}$ sao cho $T_i \le t$, được sắp xếp theo thứ tự tăng dần ($s_1 < s_2 < \dots < s_k$).
- (c) Với $j = 1$ đến $k$:
- Đặt $i \leftarrow s_j$. Sau đó hoán đổi $P_i$ và $P_{i+1}$.
- (d) Nếu $t \ge 10^{100}$, trả về $10^{100}$.
- Trả về $t$.
Hãy tìm giá trị nhỏ nhất có thể của $f(T)$ trên tất cả các dãy số nguyên dương $T$. Đảm bảo rằng tồn tại một dãy $T$ sao cho $f(T) < 10^{100}$.
Dữ liệu vào
Dữ liệu vào được cho theo định dạng sau:
N P_1 P_2 ... P_N
- Tất cả các giá trị đầu vào đều là số nguyên.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ với $i \neq j$.
Dữ liệu ra
In ra đáp án.
Ví dụ 1
4
4 2 1 3
2
Ví dụ 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Ghi chú
Trong ví dụ thứ nhất, đặt $T = (2, 1, 2)$. Tại $t = 1$, với $S = (2)$, $P$ trở thành $(4, 1, 2, 3)$. Tại $t = 2$, với $S = (1, 2, 3)$, các phép hoán đổi tuần tự làm thay đổi $P$ như sau: $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Do đó $f(T) = 2$. Vì không có dãy $T$ nào cho $f(T) < 2$, nên đáp án là $2$.