원형의 주차 타워가 있다. 주차 타워에는 \(N\)개의 칸이 원형으로 있다. 각 칸은 시계 방향으로 차례대로 \(1\)번째, \(2\)번째, \(\dots\), \(N\)번째 칸으로 부른다. 각 칸에는 차가 한 대씩 들어있다. \(i\)번째 칸에 있는 차는 번호 \(a_i\)를 가지고 있다.

주차 타워에는 두 개의 버튼이 있다. 버튼 A를 누르면 주차 타워를 시계방향으로, 버튼 B를 누르면 주차 타워를 반시계방향으로 한 칸 회전할 수 있다. 아래에 있는 왼쪽 그림은 위 예시에서 버튼 A를, 오른쪽 그림은 버튼 B를 누른 다음의 상태를 나타낸다.

이 때, 주차 타워에서 모든 차를 빼려 한다.

맨 아래에 있는 한 개의 칸에서만 차를 뺄 수 있다. 초기 상태에는 \(1\)번째 칸이 맨 아래에 있다. 맨 아래에 있지 않은 칸에 있는 차를 빼기 위해서는, 먼저 버튼을 적절히 눌러서 주차 타워를 회전해, 차가 있는 칸을 맨 아래로 옮겨야 한다.

추가적으로, 번호 \(x\)를 가진 차를 빼기 위해서는 먼저 번호가 \(x\)보다 작은 모든 차를 먼저 빼어야 한다. 즉, 주차 타워에 번호가 \(x\) 미만인 차가 남아 있다면, 번호가 \(x\)인 차를 뺄 수 없다.

주차 타워에서 모든 차를 빼기 위해, 버튼을 눌러야 하는 총 횟수의 최솟값을 구하는 프로그램을 작성하여라.

• \(1 \le N \le 100\,000\)
• \(1 \le a_i \le 1\,000\,000\,000\)

첫 번째 줄에 정수 \(N\)이 주어진다.

두 번째 줄에 차들의 번호 \(a_1, \dots , a_N\)이 순서대로 공백을 사이에 두고 주어진다.

첫 번째 줄에 버튼을 눌러야 하는 총 횟수의 최솟값을 출력하라.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2022 > 2차 대회 > 중등부 3번