$(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) $T_i \le t$를 만족하는 모든 인덱스 $i \in \{1, \dots, N - 1\}$을 오름차순($s_1 < s_2 < \dots < s_k$)으로 나열한 수열을 $S = (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$입니다. $f(T) < 2$를 만족하는 $T$는 존재하지 않으므로 정답은 $2$입니다.