35497번 - FLYING HIGH WITH U

FLYING HIGH WITH U 난 그 날 바이킹에서

별의 별 생각을 몇 초 동안 한지 모르겠어

행복이 뭐 이리도 쉬워 벌써 이 밤이 아쉬워

빈첸 - FLYING HIGH WITH U 中

영인이는 바이킹을 타며 별의 별 생각에 잠겼다. 영인이의 머릿속은 $1$번째 칸부터 $N$번째 칸까지 총 $N$개의 연속된 칸으로 이루어져 있다. 각 생각은 머릿속에서 하나의 연속된 구간을 차지하며, 여러 생각이 같은 칸을 동시에 차지할 수도 있다.

$i$번째 생각은 구간 $[l_i, r_i]$를 차지하며, $l_i \le j \le r_i$인 모든 $j$번째 칸에 영향을 미친다. 영인이의 머릿속 상태는 $A_1, A_2, \cdots, A_N$으로 나타낼 수 있으며, $A_j$는 $j$번째 칸을 차지하는 생각의 개수이다.

영인이의 머릿속 상태가 주어졌을 때, 이 상태를 만들 수 있는 생각의 최소 개수를 구해보자.

예를 들어 머릿속 상태가

$1\ 2\ 3\ 4\ 3\ 2\ 1$

이라면, 구간 $[1,7],[2,6],[3,5],[4,4]$를 차지하는 $4$개의 생각으로 만들 수 있다. 이보다 더 적은 생각으로는 만들 수 없으므로 최소 개수는 $4$이다.

첫 번째 줄에 $N$이 주어진다.

두 번째 줄에 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

첫 번째 줄에 영인이의 머릿속 상태를 만들 수 있는 생각의 최소 개수를 출력한다.

• $1 \le N \le 100\,000$
• $0 \le A_j \le 1\,000$