Candy

Hard

There are n children with ratings. Each child gets at least one candy, and a child with a higher rating than an adjacent child must get more candies. Return the minimum total candies.

Example 1

Input:  ratings = [1,0,2]
Output: 5

Example 2

Input:  ratings = [1,2,2]
Output: 4

Constraints

• n == ratings.length
• 1 <= n <= 2*10^4
• 0 <= ratings[i] <= 2*10^4