GreedyArray
Children stand in a line, each with a rating. Every child must get at least one candy, and a child with a higher rating than a neighbour must get more candy than that neighbour. Find the minimum total number of candies.
Input
Line 1: n. Line 2: the n ratings.
Output
Print the minimum number of candies.
Constraints
1 <= n <= 2 * 10^4 0 <= rating <= 2 * 10^4
Example 1
Input
3 1 0 2
Output
5
Candies 2, 1, 2 give a total of 5.
Example 2
Input
3 1 2 2
Output
4
Candies 1, 2, 1: equal ratings do not force more candy.