oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

stagnantwater Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

stagnantwater.html

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, 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.

Input

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.

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 ≤ 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

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

Ad Hoc

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
137201s256MBMinimum
226101s256MBMinimum
324391s256MBMinimum
413501s256MBMinimum
5031s256MBMinimum

Judge Compile Command

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

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.