Children stand in a line, and ratings[i] is the rating of child i. Give them candies so that every child gets at least one, and a child with a higher rating than a neighbor gets more candies than that neighbor.
Return the minimum number of candies you need.
Examples
Example 1
- Input
- ratings = [1, 0, 2]
- Output
- 5
- Why
- Give 2, 1 and 2 candies.
Example 2
- Input
- ratings = [1, 2, 2]
- Output
- 4
- Why
- Give 1, 2 and 1. The third child has the same rating as the second, so it can have fewer.
Constraints
1 <= ratings.length <= 2 * 10^40 <= ratings[i] <= 2 * 10^4