시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 217 57 52 31.325%

문제

알고리즘 게임 행사의 성대한 개최를 위하여, 일렬로 들어선 타워들의 철거를 하려고 한다. 최초 계획은 각 타워를 구성하는 블록을 폭파시키려 했지만 시간 문제로 조금 더 빠른 방법이 필요하다.

상근이에게는 블록들의 빠른 제거를 위하여 Kinetic / Incandescent Energy Particle Cannon(이하 UKIEPC)가 주어졌다. UKIEPC는 한번의 충전으로 타워 하나의 모든 층 또는 상근이가 선택한 모든 타워들의 x번째 층을 동시에 제거 할 수있다. 후자의 경우에는 만약 상근이가 선택한 x 보다 높이가 낮은 블록들은 그대로 남아 있고, 그보다 높은 경우에는 x번째 층이 제거되며 나머지 블록들은 한층씩 아래로 내려온다.

각 타워들의 층수가 주어질 때, 모든 블록들을 제거하기 위한 최소의 UKIEPC 충전 횟수를 구하시오.

입력

첫줄에는 타워의 수 n(2 ≤ n ≤ 100 000)가, 두번째 줄에는 n개의 타워에 대한 각각의 블록의 수 hi ( i = 1, 2, ... , n, 1 ≤ hi ≤ 1 000 000)가 주어진다.

출력

출력은 하나의 줄에 모든 블록을 제거할 수 있는 최소의 충전 횟수를 출력 하시오.

예제 입력

6
2 1 8 8 2 3

예제 출력

5

예제 입력 2

5
1 1 1 1 10

예제 출력 2

2

힌트

hi 높이를 가지는 타워는 총 hi 개 블록으로 구성됨 (1* hi 모양의 직사각형)