أُعطيَ لك تبديل $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$.