给你一个 $(1, 2, \dots, N)$ 的排列 $P = (P_1, P_2, \dots, P_N)$。

对于一个长度为 $N - 1$ 的正整数序列 $T = (T_1, T_2, \dots, T_{N-1})$，值 $f(T)$ 定义为以下过程的返回值。

过程 $f(T)$

1. $t \leftarrow 0$。

2. 当 $P$ 未按升序排序时：

   (a) $t \leftarrow t + 1$。 (b) 令 $S = (s_1, s_2, \dots, s_k)$ 为所有满足 $T_i \le t$ 的下标 $i \in \{1, \dots, N - 1\}$ 按升序排列组成的序列（即 $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}$。

3. 返回 $t$。

求在所有正整数序列 $T$ 中，$f(T)$ 的最小可能值。保证存在一个序列 $T$ 使得 $f(T) < 10^{100}$。

输入格式

输入格式如下：

$N$

$P_1$ $P_2$ $\dots$ $P_N$

• 所有输入值均为整数。
• $2 \le N \le 5000$。
• $1 \le P_i \le N$。
• 对于 $i \neq j$，$P_i \neq P_j$。

输出格式

输出答案。

样例

输入样例 1

4
4 2 1 3

输出样例 1

2

输入样例 2

20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14

输出样例 2

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$。