I. Improvised Handles
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A craft shop in Ioannina keeps $$$n$$$ boxes tightly packed in a single row inside an open-top organizer. The boxes have the same width, and box $$$i$$$ has height $$$h_i$$$.

A box can only be removed by lifting it straight up. To lift a box without a handle, you must grip both of its sides near the top. You can do this if and only if each of its two immediate neighbors in the original row has already been removed or is strictly shorter than the chosen box. There is no obstacle beyond either end of the row.

After a box is removed, its place stays empty. The other boxes do not move, and boxes separated by an empty place do not become neighbors. You cannot tilt the boxes or slide them sideways.

Before removing any boxes, you may attach a paper tab to the top of any box. A box with a tab can be lifted out at any time, regardless of its neighbors' heights. Each tab belongs to one box and cannot be moved to another.

Find the minimum number of tabs that allow you to remove all boxes, choosing the removal order yourself.

Input

The first line contains an integer $$$n$$$ ($$$1\le n\le 200\,000$$$), the number of boxes.

The second line contains $$$n$$$ integers $$$h_1,h_2,\ldots,h_n$$$ ($$$1\le h_i\le 10^9$$$), the heights of the boxes. Heights are not necessarily distinct.

Output

Print one integer: the minimum number of paper tabs needed.

Examples
Input
8
5 5 5 5 5 2 2 3
Output
3
Input
3
1 2 1
Output
0
Input
1
1000000000
Output
0
Note
First example: attach tabs to boxes $$$2$$$, $$$4$$$, and $$$7$$$, and remove these boxes.
Then remove boxes $$$1,3,5,8,6$$$, in this order. Three tabs are necessary.

In the second example, no tabs are needed: remove boxes $$$2$$$, $$$1$$$, and $$$3$$$, in this order. After box $$$2$$$ is removed, boxes $$$1$$$ and $$$3$$$ do not become neighbors.