2022년도한국정보올림피아드2차대회
주차타워
원형의주차타워가있다. 주차타워에는N개의칸이원형으로있다. 각칸은시계방향으로차례대로1
번째, 2번째, . . . , N번째칸으로부른다. 각칸에는차가한대씩들어있다. i번째칸에있는차는번호ai를
가지고있다.
주차타워에는두개의버튼이있다. 버튼A를누르면주차타워를시계방향으로, 버튼B를누르면주차
타워를반시계방향으로한칸회전할수있다. 아래에있는왼쪽그림은위예시에서버튼A를, 오른쪽그림은
버튼B를누른다음의상태를나타낸다.
이때, 주차타워에서모든차를빼려한다.
맨아래에있는한개의칸에서만차를뺄수있다. 초기상태에는1번째칸이맨아래에있다. 맨아래에
있지않은칸에있는차를빼기위해서는, 먼저버튼을적절히눌러서주차타워를회전해, 차가있는칸을
맨아래로옮겨야한다.
추가적으로, 번호x를가진차를빼기위해서는먼저번호가x보다작은모든차를먼저빼어야한다. 즉,
주차타워에번호가x 미만인차가남아있다면, 번호가x인차를뺄수없다.
주차타워에서모든차를빼기위해, 버튼을눌러야하는총횟수의최솟값을구하는프로그램을작성하
여라.
제약조건
• 1 ≤N ≤100 000
• 1 ≤ai ≤1 000 000 000
2022년도한국정보올림피아드2차대회

부분문제
1. (8점) ai = 1. (1 ≤i ≤N), 즉, 모든자동차의번호는1이다.
2. (9점) i̸ = j일때, ai̸ = aj. 즉, 모든자동차의번호가다르다.
3. (10점) N ≤10.
4. (21점) N ≤100.
5. (31점) N ≤1 000.
6. (21점) 추가제약조건없음.
입력형식
첫번째줄에정수N이주어진다.
두번째줄에차들의번호a1, · · · , aN이순서대로공백을사이에두고주어진다.
출력형식
첫번째줄에버튼을눌러야하는총횟수의최솟값을출력하라.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2022 > 2차 대회 > 정보올림피아드위원회