A gardener wants to water his plants. He waters them one by one, one at a time in order. He wants to pour more water to plants which look dry. But he always pours a minimum of 1 ltr to any plant. But it feels wrong for the plants if plants which are nearby and are equally dry get the same amount of water. So for a fair distribution of water, the gardener wants to maintain that nearby/adjacent plants get differing amounts of water based on which is more dry. But water is scarce and limited, so we need to reduce amount of water spent.
When two adjacent plants are equally dry, it is not necessary that they will be poured equal amounts of water.
For example, for the sample input case (1 2 3 3) the water in litres that can be poured for every plant is: 1 2 3 1
The output is hence, 1+2+3+1=7
Here the plant 0 had dryness 1 and was poured water of 1 litres.
Plant 1 had dryness 2 and was poured water of 2 litres.
As you see plant 0 was poured less than plant 1 because its dryness was less. This requirement is only for adjacent plants.
So if plant a and plant b are not adjacent and drynessA > drynessB, then waterA need not be > waterB
Input Format
Input First line contains an integer 'n' , the number of plants. Next n line contains an integer,which represents dryness of the plants. Plants are watered in the order of they are given.
Output Format
Ouput Print an integer , i.e the minimum amount of water in litres that is to be poured.
Sample Input 0 4 1 2 3 3
Sample Output 0 7
Aucun commentaire:
Enregistrer un commentaire