프린터 헤드

Johnny는 3D 프린터를 샀다. 그는 간단한 작업으로 프린터를 시험하려 한다. 밑면이 정사각형으로 모두 같고 높이가 $1, 2, \ldots, n$인 직육면체 $n$개를 주어진 순서대로 출력하는 것이다. 프린터는 왼쪽에서 오른쪽으로, 그리고 오른쪽에서 왼쪽으로 훑으며 작동하고, 훑는 방향은 임의로 섞을 수 있다. 즉 왼쪽에서 오른쪽으로 훑는 동작을 연달아 두 번 해도 되고, 오른쪽에서 왼쪽으로 훑는 동작을 연달아 해도 된다. 한 번 훑는 동안 프린터는 임의의 개수만큼 칸 위에 멈춰 설 수 있고 각 칸마다 직육면체를 하나씩 출력한다. 처음 출력하는 직육면체의 높이는 정해져 있고, 그다음부터는 높이가 1씩 낮아진다(프린터 헤드가 식기 때문이다). 이미 무언가를 출력한 칸에는 다시 출력할 수 없다.

훑는 동작에는 돈이 든다. Johnny가 이 작업에 쓰는 훑기 횟수를 최소로 줄이도록 도와주자.

첫째 줄에 양의 정수 $n$이 하나 주어진다($1 \le n \le 10^6$). 이는 출력할 직육면체의 개수이다. 둘째 줄이자 마지막 줄에는 서로 다른 양의 정수 $n$개가 주어지며, 이는 $a_i$ ($1 \le a_i \le n$)로 나타낸다. 이는 차례로 출력할 직육면체의 높이이다.

주어진 직육면체 순서를 출력하는 데 필요한 최소 훑기 횟수를 양의 정수 하나로 출력한다.

첫 번째 예제에서 Johnny는 높이 6, 5, 4, 3인 직육면체를 오른쪽에서 왼쪽으로 훑는 동작 하나로 출력하고, 2, 1을 왼쪽에서 오른쪽으로 훑는 동작 하나로 출력할 수 있다.

두 번째 예제에서 Johnny는 높이 8, 7, 6인 직육면체를 왼쪽에서 오른쪽으로 훑는 동작 하나로 출력하고, 이어서 5, 4를 오른쪽에서 왼쪽으로 훑는 동작 하나로, 마지막으로 3, 2, 1을 역시 오른쪽에서 왼쪽으로 훑는 동작 하나로 출력할 수 있다.