Count Water Accumulation Basins

Given a series of integers representing the elevation changes along a horizon, consecutive points are connected by straight lines. A basin (or low-lying area) is a region where water can potentially accumulate. More formally, a basin is defined as a contiguous segment of the horizon that starts with a descent from a peak and then is followed by an ascent back to a level strictly higher than the lowest point in that segment. Only basins that are completely bounded on both sides by a rise (i.e. the right boundary is higher than the valley bottom) are counted.

For example, consider the elevation array \[ [0, 1, 0, 2, 1, 2, 0, 0, 2, 0] \] which when plotted looks like the image below:

This array has 3 basins where water could accumulate.

Note: Equal consecutive numbers are considered part of the descending (or ascending) sequence. A basin is counted only when there is a descent followed by an ascent (i.e. the valley is bounded by a higher elevation on the right).

inputFormat

The first line contains an integer n representing the number of points in the horizon. The second line contains n space-separated integers representing the elevation at each point.

For example:

10
0 1 0 2 1 2 0 0 2 0

outputFormat

Output a single integer which is the number of basins (low-lying areas) where water can potentially accumulate.

For the sample input above, the output should be:

3

sample

10
0 1 0 2 1 2 0 0 2 0

3