Task Po
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 cross-examination, 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? – Laa-Laa 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 Noo-Noo. 1
What number did Noo-Noo say?
Input
The first line c ontains an integer n (1 ≤ n ≤ 1 00 0 00), the length o f the sequence.
The second line contains n nonnegative integers ai (0 ≤ ai ≤ 109
), the sequence after Po’s enhancements.
Output
Output m, the minimum possible number of enhancements.
Examples
input
3
2 2 2
output
1
input
5
2 3 3 3 2
output
2
input
6
1 2 3 2 1 3
output
4
Clarification of the second example:
Po first increased all elements of the sequence by 2, and then increased the middle three by 1.

有没有谁知道这个题的原题啊