파일 업로드

점심시간 줄 정리

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

학교에서 아이들이 점심식사를 먹기 전에 줄을 세우려고 합니다. 현재 NN 명의 학생들 (1N1001 \leq N \leq 100)이 줄을 서 있고, 이들은 편리하게 1N1 \dots N까지 번호가 매겨져 있습니다. 

지금 학생들은 p1,p2,p3,,pNp_1, p_2, p_3, \dots, p_N의 순서로 줄을 서 있고, 선생님은 p1p_1 학생 앞에 서 있습니다. 선생님은 학생들을 1,2,3,,N1, 2, 3, \dots, N의 순서로 재정렬하려고 합니다, 이때 11번 학생이 선생님 바로 옆에 있어야 합니다.

오늘 학생들은 조금 졸린 상태이므로, 어느 시점에서든 선생님의 지시를 주의 깊게 듣고 있는 학생은 선생님 바로 앞에 있는 학생 뿐입니다. 한 시간 단계에서, 선생님은 이 학생에게 줄에서 kk 만큼 이동하라고 지시할 수 있으며, 이때 kk1N11 \ldots N-1 범위 안에 있습니다. kk명의 학생들은 앞으로 움직여, 이동하는 학생이 그들 뒤에 자리잡을 수 있도록 자리를 만들어 줍니다.

예를 들어, N=4N=4이고 학생들이 다음과 같은 순서로 시작한다고 가정해 봅시다:

선생님 : 4, 3, 2, 1

선생님에게 주의를 기울이는 유일한 학생은  44 학생입니다. 만약 선생님이 그 학생에게 줄을 따라 22 걸음 이동하도록 지시하면, 순서는 다음과 같아질 것입니다:

선생님 : 3, 2, 4, 1

이제 선생님에게 주의를 기울이는 유일한 학생은 33 학생이므로, 두 번째 시간 단계에서 선생님은 33 학생에게 지시를 내릴 수 있으며, 학생들이 정렬될 때까지 이러한 과정을 계속할 수 있습니다.

선생님은 정렬을 완료하고 빨리 아침 식사를 먹으러 가려고 합니다. 선생님이 학생들을 정렬하는데 필요한 최소 시간 단계 수를 찾아주십시오.

💻 입력

입력의 첫 번째 줄에는 NN이 포함됩니다.

두번째 줄에는 NN개의 공백으로 구분된 정수, p1,p2,p3,,pNp_1, p_2, p_3, \dots, p_N이 주어지며, 이는 학생들의 시작 순서를 나타냅니다.

🖨️ 출력

단일 정수: 선생님이 최선을 다한 경우 NN명의 학생이 정렬된 순서로 정렬되기 전의 시간 단계 수.


💻 예제 입력 1
4
1 2 4 3
🖨️ 예제 출력 1
3

출처: USACO 2019 January Contest, Bronze Problem 2. Sleepy Cow Sorting