Вам дано перестановку $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$.