You are given a permutation $P = (P_1, P_2, \dots, P_N)$ of $(1, 2, \dots, N)$.
For a sequence of positive integers $T = (T_1, T_2, \dots, T_{N-1})$ of length $N - 1$, the value $f(T)$ is defined as the return value of the following procedure.
Procedure $f(T)$
- $t \leftarrow 0$.
- While $P$ is not sorted in ascending order:
- (a) $t \leftarrow t + 1$.
- (b) Let $S = (s_1, s_2, \dots, s_k)$ be the sequence of all indices $i \in \{1, \dots, N - 1\}$ such that $T_i \le t$, sorted in increasing order ($s_1 < s_2 < \dots < s_k$).
- (c) For $j = 1$ to $k$:
- Let $i \leftarrow s_j$. Then swap $P_i$ and $P_{i+1}$.
- (d) If $t \ge 10^{100}$, return $10^{100}$.
- Return $t$.
Find the minimum possible value of $f(T)$ over all sequences $T$ of positive integers. It is guaranteed that there exists a sequence $T$ such that $f(T) < 10^{100}$.
Input
The input is given in the following format:
N P_1 P_2 ... P_N
- All input values are integers.
- $2 \le N \le 5000$.
- $1 \le P_i \le N$.
- $P_i \neq P_j$ for $i \neq j$.
Output
Output the answer.
Sample 1
4
4 2 1 3
2
Sample 2
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39
Note
In the first example, let $T = (2, 1, 2)$. At $t = 1$, with $S = (2)$, $P$ becomes $(4, 1, 2, 3)$. At $t = 2$, with $S = (1, 2, 3)$, sequential swaps change $P$ as $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$. Thus $f(T) = 2$. Since no $T$ yields $f(T) < 2$, the answer is $2$.