실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
학교에서 아이들이 점심식사를 먹기 전에 줄을 세우려고 합니다. 현재 명의 학생들 ()이 줄을 서 있고, 이들은 편리하게 까지 번호가 매겨져 있습니다.
지금 학생들은 의 순서로 줄을 서 있고, 선생님은 학생 앞에 서 있습니다. 선생님은 학생들을 의 순서로 재정렬하려고 합니다, 이때 번 학생이 선생님 바로 옆에 있어야 합니다.
오늘 학생들은 조금 졸린 상태이므로, 어느 시점에서든 선생님의 지시를 주의 깊게 듣고 있는 학생은 선생님 바로 앞에 있는 학생 뿐입니다. 한 시간 단계에서, 선생님은 이 학생에게 줄에서 만큼 이동하라고 지시할 수 있으며, 이때 는 범위 안에 있습니다. 명의 학생들은 앞으로 움직여, 이동하는 학생이 그들 뒤에 자리잡을 수 있도록 자리를 만들어 줍니다.
예를 들어, 이고 학생들이 다음과 같은 순서로 시작한다고 가정해 봅시다:
선생님 : 4, 3, 2, 1
선생님에게 주의를 기울이는 유일한 학생은 학생입니다. 만약 선생님이 그 학생에게 줄을 따라 걸음 이동하도록 지시하면, 순서는 다음과 같아질 것입니다:
선생님 : 3, 2, 4, 1
이제 선생님에게 주의를 기울이는 유일한 학생은 학생이므로, 두 번째 시간 단계에서 선생님은 학생에게 지시를 내릴 수 있으며, 학생들이 정렬될 때까지 이러한 과정을 계속할 수 있습니다.
선생님은 정렬을 완료하고 빨리 아침 식사를 먹으러 가려고 합니다. 선생님이 학생들을 정렬하는데 필요한 최소 시간 단계 수를 찾아주십시오.
입력의 첫 번째 줄에는 이 포함됩니다.
두번째 줄에는 개의 공백으로 구분된 정수, 이 주어지며, 이는 학생들의 시작 순서를 나타냅니다.
단일 정수: 선생님이 최선을 다한 경우 명의 학생이 정렬된 순서로 정렬되기 전의 시간 단계 수.
4 1 2 4 3
3
출처: USACO 2019 January Contest, Bronze Problem 2. Sleepy Cow Sorting