시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1546 | 946 | 818 | 68.053% |
동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고 현재 뒤죽박죽 되어있는 순서를 왼쪽부터 오른쪽으로 순서대로 1∼N번의 책들로 재배열하길 원한다.
동혁이가 책들을 배열하는 방법은 어떠한 책 하나를 꺼내서 다른 위치에 꽂는 방법이다.
1 5 2 3 4
위와 같이 책이 배열되어 있을 때 5번 책을 꺼내 가장 뒤쪽에 꼽으면
1 2 3 4 5
로 배열되고, 1∼5번까지 순서대로 책이 꽂히면서 정리는 끝나게 된다.
문제는 현재 책들의 배열순서가 주어지면 최소 횟수로 책들을 옮겨 책 정리를 끝내는 것이다.
첫째 줄에 책의 개수 N(1 ≤ N ≤ 200,000)이 주어진다. 두 번째 줄에는 현재 책들이 배열된 순서가 공백으로 구분되어 주어진다.
동혁이가 책들을 옮겨야 하는 최소 횟수를 출력한다.
5 2 1 4 5 3
2