Tinky Winky left a sequence of \(n\) zeroes in the Tubbytronic Superdome, and left for a walk
with Dipsy. When he came back, he saw that a misdeed has been done. The sequence was
changed, and Po was smiling mischeviously in the corner of the room.
\(Oh\) dear! Po, what have you done?! – asked Tinky Winky in horror.
\(I\) enhanced the sequence! – replied Po.
After cro\(ss-ex\)amination, it was established that Po did a number of enhancements on the sequence. In
every enhancement, she took a segment of a sequence and increased all elements in the segment by
some positive integer. Also, every two segments were either disjoint or one was completely contained in
other.
How many enhancements have you done, Po? – L\(aa-La\)a inquired.
\(I\) really don’t know! I’m only sure \(I\) did the minimum number \(of\) enhancements possible \(to\) get this
sequence! – said Po exhaustedly.
Then \(it\) surely must \(be\) \(m\)! – proclaimed N\(oo-No\)o. ^{1}
What number did N\(oo-No\)o say?

In test cases worth 30 points, it holds \(1 \le n \le 1000\).

The first line contains an integer \(n\) (\(1 \le n \le 100\,000\)), the length of the sequence.
The second line contains \(n\) nonnegative integers \(a_{i}\) (\(0 \le a_{i} \le 10^{9}\)), the sequence after Po’s enhancements.

Output \(m\), the minimum possible number of enhancements.

생성자가 기록되지 않았습니다.

출처 COCI 2020/2021 Contest 5