급식판 비우기

문제

학교 급식실에는 한 줄로 늘어선 N개의 칸이 있는 긴 급식판이 있다. 왼쪽부터 i번째 칸에는 음식이 a_i만큼 담겨 있다. 배식이 끝난 뒤 조리사는 이 급식판을 완전히 비워야 하며, 한 번의 작업으로 다음 두 가지 중 하나를 할 수 있다. 1. 연속한 칸 구간을 하나 골라, 그 구간에 속한 모든 칸의 음식을 동시에 1씩 덜어 낸다. 단, 구간 안의 모든 칸에는 음식이 1 이상 남아 있어야 한다. 2. 칸 하나를 골라 그 칸의 음식을 남은 양과 상관없이 한 번에 모두 비운다. 두 작업은 어떤 순서로든 섞어서 쓸 수 있다. 모든 칸의 음식이 0이 되도록 하는 데 필요한 작업 횟수의 최솟값을 구하시오. 처음부터 0인 칸은 그대로 두어도 된다. 예를 들어 칸이 하나뿐이고 음식이 5라면 2번 작업 한 번이면 충분하므로 답은 1이다. 답은 항상 N 이하이므로 32비트 정수 범위 안에 들어간다.

입력

첫째 줄에 칸의 수 N(1 ≤ N ≤ 200,000)이 주어진다. 둘째 줄에 a_1, a_2, ..., a_N(0 ≤ a_i ≤ 1,000,000,000, 정수)이 공백으로 구분되어 주어진다.

출력

모든 칸을 비우는 데 필요한 최소 작업 횟수를 한 줄에 출력한다.

5
3 1 2 1 3

4

1
5

1

4
2 2 2 2

2

출처: Devin.KR 자체 제작