#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Ever since the recent Zika Virus outbreak, Rar the Cat has been very concerned about mosquito breeding. Rar the Cat has learnt that mosquito likes to breed in stagnant water, and has set out to eliminate them.

Unfortunately for Rar the Cat, he possesses a rather large area of land. However, this land forms a straight line but have varying heights. To illustrate the varying heights, Rar the Cat has segmented the land into **N** segments, such that each segment has its own height, **H _{i}**.

During a rain, water puddles would be formed in this area of land. However, as water naturally flows from a higher place to a lower place, it is observed that rainwater from a higher segment will flow to its adjacent segment if it is lower or equal. For example, if segment 1, 2 and 3 have heights 3, 2 and 5 respectively: rainwater that falls on segment 1 will flow to segment 2, rainwater that falls on segment 3 will also flow to segment 2. In this case, the rainwater in segment 2 cannot flow anywhere, hence forming a puddle of stagnant water.

In the case of segment 1, 2 and 3 having heights 3, 5 and 7 respectively, no stagnant water puddle will be formed as water in segment 1 will flow out of Rar the Cat's area. (Which means it is not his problem anymore :P) Similarly, there will not be a stagnant water puddle for 3 segments with heights 7, 5, 3 respectively.

## Input

The first line of input will contain one integer, **N**.

The second line of input will contain **N** integers, with the **i**th integer being **H _{i}**.

## Output

The output should contain one integer, the total number of stagnant water puddles that will form in Rar the Cat's plot of land.

## Limits

For all testcases: 0 ≤ **H _{i}** ≤ 10

^{9}

Subtask 1 (37%): 1 ≤ **N** ≤ 2000.

Subtask 2 (26%): 1 ≤ **N** ≤ 200000. In addition, no two segments will have the same height.

Subtask 3 (24%): 1 ≤ **N** ≤ 200000.

Subtask 4 (13%): 1 ≤ **N** ≤ 2000000.

Subtask 5 (0%): Sample Testcases

## Sample Testcase 1

### Input

3 3 2 5

### Output

1

### Explanation

One stagnant water puddle will form at segment 2.

## Sample Testcase 2

### Input

5 7 5 6 5 7

### Output

2

### Explanation

Two stagnant water puddles will form: one at segment 2, one at segment 4.

## Sample Testcase 3

### Input

8 3 2 2 3 2 2 1 4

### Output

2

### Explanation

One stagnant water puddle will form at segments 2-3. Another stagnant water puddle will form at segment 7.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 37 | 20 | 1s | 256MB | Minimum |

2 | 26 | 10 | 1s | 256MB | Minimum |

3 | 24 | 39 | 1s | 256MB | Minimum |

4 | 13 | 50 | 1s | 256MB | Minimum |

5 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o stagnantwater -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512