주차 타워

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

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

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

차는 맨 아래에 있는 한 칸에서만 뺄 수 있다. 처음에는 1번째 칸이 맨 아래에 있다. 맨 아래에 있지 않은 칸의 차를 빼려면, 먼저 버튼을 적절히 눌러 주차 타워를 회전해서 그 차가 있는 칸을 맨 아래로 옮겨야 한다.

또한 번호 $x$를 가진 차를 빼려면, 먼저 번호가 $x$보다 작은 모든 차를 빼야 한다. 즉, 주차 타워에 번호가 $x$ 미만인 차가 남아 있으면 번호가 $x$인 차는 뺄 수 없다.

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

첫 번째 줄에 정수 $N$이 주어진다.

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

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

• $1 ≤ N ≤ 100,000$
• $1 ≤ a_i ≤ 1,000,000,000$