Сізге $(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)$
- $t \leftarrow 0$.
- $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}$ мәнін қайтару.
- $t$ мәнін қайтару.
Барлық оң бүтін сандар тізбектері $T$ бойынша $f(T)$-ның ең кіші мүмкін мәнін табыңыз. $f(T) < 10^{100}$ болатындай $T$ тізбегі бар екеніне кепілдік беріледі.
Кіріс деректер
Кіріс деректер келесі форматта беріледі:
N P_1 P_2 ... 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
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$ болады.