Walls

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka approached an abandoned building in which only \(n\) walls, located one after another, have survived. The height of the \(i\)-th wall is equal to \(h_i\).

Zenyk loves climbing walls very much, and Marichka decided to wait for him. The girl is waiting for him behind the last wall. Zenyk wants to be able to see Marichka from every wall. To do this, he can make holes in the walls.

In order for Zenyk to be able to see Marichka from the \(i\)-th wall, there must exist such a height \(y \in [0, h_i]\) that for any wall \(j>i\), either \(h_j \le y\) or there is a hole in this wall at height \(y\). The value of \(y\) can be non-integer. Also note that if the height of some wall is equal to \(y\), then Zenyk can see through this wall and no additional hole needs to be made. Zenyk is interested in the minimum number of holes he needs to make to see Marichka from every wall.

Input

The first line contains a single integer \(n\).

The second line contains \(n\) integers \(h_i\) — the heights of the walls.

Output

Print a single number — the minimum required number of holes.

Constraints

\(1 \le n \le 2 \cdot 10^5\),

\(1 \le h_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 9 9 5 2 1 3 7	3

Notes

In the example, you can make 3 holes: a hole at height 1 in the last two walls and at height 4.7 in the last wall.