נתונה תמורה $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$.