0143. Dams

Input file name:	dams.in
Output file name:	dams.out
Time limit:	1 s
Memory limit:	64 megabytes

Poor Vellabadzhio villagers got too tired of the constant floods during their holidays. No matter this gives them an opportunity to advertise certain chemicals and earn a lot of money for their daily activities, they want to get rid of this disaster. To solve the problem several dams were raised close to the very high hill from which the water comes into the village. One very clever engineer has decided that the more dams they raise, the more water they will hold. Each mini-dam is nevertheless below the hill, thus making fluids possible anyway. Now, given heights of each dam, you are to evaluate the total capacity of such strange water storage. The surface between two consecutive dams is 1 square unit. Thickness of each dam is 0 linear units.

Input file

1st line: n (amount of dams), 1 ≤ n ≤ 500'000
2nd line: dam heights (left to right), 0 ≤ hi ≤ 1'000'000'000, i = 1..n

Output file

m which stands for the water storage capacity

Examples:

dams.in	dams.out
3 30 20 10	60

Source: Petrozavodsk Summer 2003. Trinity Contest, Tuesday, August 26
Author: Denis Koshman

Discuss       Submit a solution



Printable version