Po

면접 대비

시간 제한1초메모리 제한512 MB

요약

모두 0인 배열에서 시작해 서로 겹치지 않거나 포함 관계인 구간에 양의 정수를 더해 만든 배열이 주어질 때, 필요한 최소 구간 연산 횟수를 구한다.

문제

Tinky Winky는 Tubbytronic Superdome에 길이 $n$ 인 0 수열을 두고 Dipsy와 산책을 나갔다. 돌아와 보니 못된 짓이 저질러져 있었다. 수열이 바뀌어 있었고, Po가 방 한구석에서 짓궂게 웃고 있었다.

이런! Po, 네가 무슨 짓을 한 거야?! 라고 Tinky Winky가 겁에 질려 물었다.

나는 수열을 향상시켰어! 라고 Po가 대답했다.

추궁 끝에, Po가 수열에 여러 번의 향상을 했다는 사실이 밝혀졌다. 향상 한 번마다 그녀는 수열의 구간 하나를 잡고 그 구간의 모든 원소를 어떤 양의 정수만큼 증가시켰다. 또한 임의의 두 구간은 서로 겹치지 않거나, 한쪽이 다른 쪽에 완전히 포함되었다.

Po, 향상을 몇 번이나 한 거야? 라고 Laa-Laa가 물었다.

정말 모르겠어! 이 수열을 얻기 위해 가능한 최소 횟수의 향상만 했다는 것만 확실해! 라고 Po가 지쳐서 말했다.

그럼 분명히 $m$ 이겠네! 라고 Noo-Noo가 선언했다. (Noo-Noo는 Teletubbies의 청소기 애완동물이다)

Noo-Noo가 말한 수는 무엇일까?

첫째 줄에 수열의 길이 $n$ 이 주어진다 ( $1 \le n \le 100\,000$ ).

둘째 줄에 Po의 향상 후 수열인 $n$ 개의 음이 아닌 정수 $a_i$ 가 주어진다 ( $0 \le a_i \le 10^9$ ).

가능한 향상 횟수의 최솟값 $m$ 을 출력한다.