Po

Interview

Time limit1sMemory limit512 MB

Summary

Given a nonnegative array built by adding positive values to nested or disjoint segments starting from zeros, find the minimum number of such segment additions needed.

Level: Medium6 of 10
Topics: Greedy, Stack, Array, Implementation
Solved: No attempts yet

Problem

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 had been done. The sequence was changed, and Po was smiling mischievously 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 the 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 the 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. (Noo-Noo is the Teletubbies' vacuum cleaner pet)

What number did Noo-Noo say?

Input

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

Output $m$ , the minimum possible number of enhancements.

Examples3

Example 1
Input
```
3
2 2 2
```
Expected output
```
1
```
Example 2
Input
```
5
2 3 3 3 2
```
Expected output
```
2
```
Example 3
Input
```
6
1 2 3 2 1 3
```
Expected output
```
4
```