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, Hi.
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.
The first line of input will contain one integer, N.
The second line of input will contain N integers, with the ith integer being Hi.
The output should contain one integer, the total number of stagnant water puddles that will form in Rar the Cat's plot of land.
For all testcases: 0 ≤ Hi ≤ 109
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
3 2 5
One stagnant water puddle will form at segment 2.
Sample Testcase 2
7 5 6 5 7
Two stagnant water puddles will form: one at segment 2, one at segment 4.
Sample Testcase 3
3 2 2 3 2 2 1 4
One stagnant water puddle will form at segments 2-3. Another stagnant water puddle will form at segment 7.