Anda diberikan sebuah permutasi $P = (P_1, P_2, \dots, P_N)$ dari $(1, 2, \dots, N)$.
Untuk sebuah barisan bilangan bulat positif $T = (T_1, T_2, \dots, T_{N-1})$ dengan panjang $N - 1$, nilai $f(T)$ didefinisikan sebagai nilai kembalian dari prosedur berikut.
Prosedur $f(T)$
- $t \leftarrow 0$.
- Selama $P$ belum terurut secara menaik:
- (a) $t \leftarrow t + 1$.
- (b) Misalkan $S = (s_1, s_2, \dots, s_k)$ adalah barisan semua indeks $i \in \{1, \dots, N - 1\}$ sedemikian sehingga $T_i \le t$, yang diurutkan secara menaik ($s_1 < s_2 < \dots < s_k$).
- (c) Untuk $j = 1$ hingga $k$:
- Misalkan $i \leftarrow s_j$. Kemudian tukar $P_i$ dan $P_{i+1}$.
- (d) Jika $t \ge 10^{100}$, kembalikan $10^{100}$.
- Kembalikan $t$.
Carilah nilai minimum yang mungkin dari $f(T)$ di antara semua barisan bilangan bulat positif $T$. Dijamin bahwa terdapat sebuah barisan $T$ sedemikian sehingga $f(T) < 10^{100}$.
Masukan
Masukan diberikan dalam format berikut:
N P_1 P_2 ... P_N
- Semua nilai masukan adalah bilangan bulat.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ untuk $i \neq j$.
Keluaran
Keluarkan jawabannya.
Contoh 1
4
4 2 1 3
2
Contoh 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Catatan
Pada contoh pertama, misalkan $T = (2, 1, 2)$. Pada $t = 1$, dengan $S = (2)$, $P$ menjadi $(4, 1, 2, 3)$. Pada $t = 2$, dengan $S = (1, 2, 3)$, pertukaran berurutan mengubah $P$ menjadi $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Dengan demikian $f(T) = 2$. Karena tidak ada $T$ yang menghasilkan $f(T) < 2$, jawabannya adalah $2$.