블록 게임

블록 $N$개가 일렬로 놓여 있다. 가장 왼쪽 블록이 1번이고 그 오른쪽 블록이 2번이며, 같은 방식으로 가장 오른쪽 블록이 $N$번이다. $i$번 블록의 높이는 $H_i$이다.

블록 앞에는 작은 기계가 한 대 놓여 있다. 처음에 기계는 1번 블록 앞에 있다. 목표는 이 기계로 블록을 모두 제거하는 것이다. 제거한 순서대로 높이를 적은 수열은 비내림차순이어야 한다.

기계에 내릴 수 있는 명령은 세 가지이다.

• 오른쪽 블록으로 이동한다. $i$번 블록 앞에 있었으면 $i+1$번 블록 앞으로 간다. 오른쪽에 블록이 없으면 이 명령을 내릴 수 없다.
• 왼쪽 블록으로 이동한다. $i$번 블록 앞에 있었으면 $i-1$번 블록 앞으로 간다. 왼쪽에 블록이 없으면 이 명령을 내릴 수 없다.
• 기계 앞에 있는 블록을 제거하고 왼쪽이나 오른쪽 블록으로 이동한다. 제거한 뒤 이동할 방향도 명령을 내릴 때 함께 정한다. 제거하고 나서 양쪽에 블록이 하나도 남지 않으면 이동하지 않아도 된다.

블록을 제거하면 남은 블록의 번호가 다시 매겨진다. 예를 들어 높이가 왼쪽부터 $(2, 3, 4, 5, 6)$이고 기계가 높이 4인 블록 앞에 있다고 하자. 높이가 4인 블록은 왼쪽에서 세 번째이므로 3번이다. 이 블록을 제거하고 왼쪽으로 이동하면 높이는 $(2, 3, 5, 6)$이 되고 기계는 높이 3인 블록, 즉 2번 블록 앞에 있게 된다. 오른쪽으로 이동하면 높이는 똑같이 $(2, 3, 5, 6)$이 되고 기계는 높이 5인 블록, 즉 3번 블록 앞에 있게 된다.

목표를 달성하는 데 필요한 명령의 최소 횟수를 구하는 프로그램을 작성하시오.

길이가 $K$인 수열 $A_1, A_2, \dots, A_K$가 $A_1 \le A_2 \le \dots \le A_K$를 만족하면 비내림차순이라고 한다.

첫째 줄에 블록의 개수 $N$이 주어진다. ($1 \le N \le 100000$)

둘째 줄에 블록의 높이 $H_1, H_2, \dots, H_N$이 순서대로 주어진다. ($1 \le H_i \le 100000$)

첫째 줄에 목표를 달성하는 데 필요한 명령의 최소 횟수를 출력한다.

첫 번째 예제는 다음과 같이 명령하면 된다. 기계 앞에 있는 블록을 대괄호로 표시한다.

• 처음 상태: [1] 2 3
• 제거하고 오른쪽으로 이동: [2] 3
• 제거하고 오른쪽으로 이동: [3]
• 제거

두 번째 예제는 다음과 같이 명령해야 한다.

• 처음 상태: [4] 2 1 3
• 오른쪽으로 이동: 4 [2] 1 3
• 오른쪽으로 이동: 4 2 [1] 3
• 제거하고 왼쪽으로 이동: 4 [2] 3
• 제거하고 오른쪽으로 이동: 4 [3]
• 제거하고 왼쪽으로 이동: [4]
• 제거