PitCraft game takes place in a two-dimensional world, which consists of blocks measuring 1 by 1 meter.
The player's island is a set of columns of varying heights, made up of stone blocks and surrounded by the sea.
A heavy rain fell over the island, which filled all the lowlands with water, and the water that did not fit in them glassed into the sea without increasing its level. Based on the landscape of the island, determine how many blocks of water are left after the rain in the lowlands on the island.
Input data format
The first line contains a natural number N (0 <= N <= 100,000) the number of columns defining the landscape of the island.
The second line contains N natural numbers Hi (1 <= Hi <= 109) column heights.
Output format
Output one number the number of blocks occupied by water.
Rating system
Solutions that work correctly with N <= 100 will score at least half of the points.
|
Enter |
Output |
11
2 5 2 3 6 9 3 1 3 4 6
|
18 |
Note
The example matches the picture. Stone is marked in black, gray water.
