채소 키우기는 즐거워 4

비타로는 정원 가꾸기를 좋아한다. 지금 정원에서 비바허브라는 식물을 기르고 있다. 정원에는 비바허브가 N그루 있고, 서쪽에서 동쪽으로 일렬로 심겨 있다. 비바허브에는 서쪽에서 동쪽으로 1부터 N까지 번호가 붙어 있다. 현재 비바허브 i (1 ≤ i ≤ N)의 높이는 Ai이다.

품종 개량 덕분에 비타로가 비바허브에 물을 한 번 주면 높이가 1만큼 자란다. 정원을 꾸미고 싶은 비타로는 다음 조건을 만족하도록 비바허브에 여러 번 물을 줄 것이다.

• 비타로가 물을 다 준 뒤 비바허브 i의 높이를 Bi라 하자. 이때 어떤 정수 k (1 ≤ k ≤ N)가 존재하여, 모든 1 ≤ j ≤ k − 1에 대해 Bj < Bj+1이고, 모든 k ≤ j ≤ N − 1에 대해 Bj > Bj+1이다.

그런데 비타로는 물을 잘 주지 못한다. 비타로는 물을 줄 때 연속한 구간의 비바허브에만 물을 줄 수 있다. 즉 정수 L과 R (1 ≤ L ≤ R ≤ N)을 골라 비바허브 L, L + 1, . . . , R에 물을 준다.

비타로는 물을 주는 횟수를 최소로 하고 싶다.

비바허브의 수와 현재 높이가 주어질 때, 위 조건을 만족하도록 하는 물 주기 횟수의 최솟값을 계산하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다. 주어지는 값은 모두 정수이다.

N
A1 · · · AN

표준 출력에 한 줄을 출력한다. 물 주기 횟수의 최솟값을 출력해야 한다.

• 2 ≤ N ≤ 200 000.
• 1 ≤ Ai ≤ 1 000 000 000 (1 ≤ i ≤ N).