AIOC Banner

Problem: Atlantis Rising

Want to try solving this problem? You can submit your code online if you log in or register.


Atlantis Rising

Input File: atlanin.txt
Output File: atlanout.txt
Time Limit: 1 second

Life in the under-sea city of Atlantis is getting rather dull. Sure, there are talking seahorses, wish-granting clams and all kinds of exotic sea life, but ultimately nothing has really happened for the past few millennia. Rumour has it that the weather is getting nice and warm up above and now King Triton has issued a royal decree--it is time for Atlantis to resurface.

There is one slight problem however--the talking seahorses, wish-granting clams and exotic sea life who live in Atlantis are not happy at the prospect of migrating to dry land. Despite their protests, the King refuses to change his mind. As a result, the citizens scramble to migrate to areas that will remain underwater when the city resurfaces.


\includegraphics[width=8cm]{atlantispre}


Atlantis is a series of flat plains with varying heights, each one unit wide as shown in the example above. When the city majestically emerges from the waves, some water may become trapped between plains, resulting in lakes where the citizens can still habitate and frolic in the cool water. Any water that can flow to the edge of Atlantis will drain away into the sea. A plain at the same height as a lake is not considered habitable by its citizens.


\includegraphics[width=8cm]{atlantis}


In the above example, once the water has settled, three units of land remain covered in seawater at positions 3, 4 and 6 from the left, and thus remain habitable. Note that although there are two units of water above position 4, this only counts as one unit of habitable land. Your task is to write a program that calculates how many habitable units of land will remain, given the shape of Atlantis.

Input

The first line of the input file will contain a single integer N, the number of units of land in all of Atlantis ( 1  <= N  <= 1000000). The following N lines describe the shape of the city from left to right. Each line will contain a single positive integer, denoting the final height of each unit of land above sea level. You are guaranteed that all heights are integers between 1 and 2000000000, inclusive.

Output

Your output file should consist of a single integer H, the number of habitable units of land after the rising of Atlantis.

Sample Input

9
1
3
2
1
4
3
5
1
1

Sample Output

3

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019,  3:20am AEST