오름차순 사진

아마추어 등반 동호회가 오늘 100번째 등정을 마쳤다. 이를 기념해 회원 전원이 한 줄로 서서 사진을 한 장 찍었다.

그런데 줄이 엉망이다. 회원들이 내키는 자리에 그냥 섰기 때문이다. 왼쪽에서 오른쪽으로 갈수록 키가 줄어들지 않도록 사진을 다시 배치하려고 한다.

그림: 첫 번째 예제의 답을 만들려고 사진을 자른 뒤 다시 붙인 모습이다.

할 수 있는 일은 인화한 사진을 이웃한 두 사람 사이에서 세로로 자르고, 잘라낸 조각을 원하는 순서로 다시 붙이는 것뿐이다. 한 조각 안에서 사람의 순서는 바뀌지 않는다.

조각을 다시 붙여 키가 왼쪽에서 오른쪽으로 감소하지 않는 한 줄을 만들 때, 필요한 자르기 횟수의 최솟값을 구하여라.

• 첫째 줄에 사진에 찍힌 사람 수 $n$이 주어진다. ($1 \le n \le 10^6$)
• 둘째 줄에 왼쪽부터 차례대로 각 사람의 키 $h_1, \dots, h_n$이 주어진다. ($1 \le h_i \le 2 \times 10^9$)

조각을 다시 붙여 키가 왼쪽에서 오른쪽으로 감소하지 않는 한 줄을 만드는 데 필요한 자르기 횟수의 최솟값을 출력한다.