졸린 소 정렬

농부 존은 소들이 아침을 먹으러 목초지로 나가기 전에, 편의상 \(1 \dots N\)번으로 번호가 매겨진 \(N\)마리의 소 (\(1 \leq N \leq 100\))를 정렬하려 하고 있다.

현재 소들은 \(p_1, p_2, p_3, \dots, p_N\)의 순서로 한 줄로 서 있고, 농부 존은 소 \(p_1\) 앞에 서 있다. 그는 소들을 재배치하여 소 \(1\)이 농부 존 옆에 오도록 \(1, 2, 3, \dots, N\)의 순서로 만들고 싶어한다.

오늘 소들은 조금 졸린 상태라서, 어느 시점에서든 농부 존의 지시에 주의를 기울이는 소는 농부 존을 바로 마주 보고 있는 소뿐이다. 한 번의 시간 단계에서, 그는 이 소에게 줄에서 \(k\)칸 뒤로 이동하라고 지시할 수 있으며, \(k\)는 \(1 \ldots N-1\) 범위의 아무 값이나 가능하다. 그 소가 지나치는 \(k\)마리의 소들은 앞으로 슬금슬금 걸어 나오고, 그 소는 그들 뒤에 끼어들 자리를 얻는다.

예를 들어 \(N=4\)이고 소들이 처음에 다음 순서로 서 있다고 하자.

 FJ: 4, 3, 2, 1

농부 존에게 주의를 기울이는 소는 소 \(4\)뿐이다. 그가 소 \(4\)에게 줄에서 \(2\)칸 뒤로 이동하라고 지시하면, 순서는 다음과 같이 된다.

 FJ: 3, 2, 4, 1

이제 농부 존에게 주의를 기울이는 소는 소 \(3\)뿐이므로, 두 번째 시간 단계에서 그는 소 \(3\)에게 지시를 내릴 수 있고, 이런 식으로 소들이 정렬될 때까지 계속한다.

농부 존은 정렬을 얼른 끝내고 농가로 돌아가 자신의 아침을 먹고 싶어한다. 소들을 정렬하는 데 필요한 최소 시간 단계 수를 구하도록 도와주자.

출제자: Dhruv Rohatgi

출제자: Dhruv Rohatgi

입력의 첫째 줄에 \(N\)이 주어진다.

둘째 줄에 소들의 시작 순서를 나타내는 \(N\)개의 정수 \(p_1, p_2, p_3, \dots, p_N\)이 공백으로 구분되어 주어진다.

정수 하나를 출력한다. 농부 존이 최적으로 행동할 때 \(N\)마리의 소가 정렬된 순서가 되기까지 걸리는 시간 단계 수이다.

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > January > Bronze