주차타워

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

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

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